c246 - 逃亡
題目描述
題目描述一個圖，其中節點代表房間，邊代表房間之間的通道，邊的權重代表通過通道所需的時間。給定一個起始房間（安全房間）和一個時間限制，要求計算在時間限制內能夠到達安全房間的房間數量。
解題思路
本題可以使用廣度優先搜尋 (BFS) 演算法來解決。由於題目要求在時間限制內到達安全房間，因此可以使用優先佇列 (Priority Queue) 來儲存待訪問的房間，優先訪問距離起始房間更近的房間。
程式碼中，dp[i] 儲存從起始房間到達房間 i 所需的最短時間。
程式碼首先讀取輸入資料，建立圖的鄰接表 e。然後，使用優先佇列 q 從起始房間開始進行 BFS。在每次迭代中，從優先佇列中取出距離起始房間最近的房間，如果到達該房間所需的時間小於或等於時間限制 t，則更新 dp[i] 的值，並將與該房間相鄰的房間加入優先佇列。
最後，統計在時間限制內能夠到達安全房間的房間數量。
複雜度分析
- 時間複雜度: O(M log N)，其中 N 是房間的數量，M 是邊的數量。這是因為 BFS 演算法需要遍歷所有邊，並且優先佇列的插入和刪除操作需要 O(log N) 的時間。
- 空間複雜度: O(N + M)，其中 N 是房間的數量，M 是邊的數量。這是因為需要儲存鄰接表和
dp陣列。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,ca,dp[105],x,y,v;
int main(){
cin >> ca;
while(ca--){
cin >> n >> s >> t >> m;
priority_queue <pair <int,int>,vector <pair <int,int>>,greater <pair <int,int>>> q;//t it
vector <pair <int,int>> e[n+1];
memset(dp,0x3f,sizeof(dp));
q.push({0,s});
for(int i=0;i<m;++i){
cin >> x >> y >> v;
e[y].push_back({x,v});
}
while(!q.empty()){
pair <int,int> tp=q.top();
int ti=tp.first,it=tp.second;
q.pop();
if(ti>t||dp[it]<=ti)continue;
dp[it]=ti;
for(int i=0;i<e[it].size();++i){
q.push({ti+e[it][i].second,e[it][i].first});
}
}
int ans=0;
for(int i=1;i<=n;++i){
if(dp[i]<=t)++ans;
}
cout << ans << "\n\n";
}
}