-
Notifications
You must be signed in to change notification settings - Fork 0
/
10986.cpp
46 lines (43 loc) · 1.3 KB
/
10986.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> ii;
#define inf 100000000
int n, m, s, t;
vector <vector <ii>> AdjList;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int cases, cas = 1, p, q, r;
cin >> cases;
while(cases--){
AdjList.clear();
cin >> n >> m >> s >> t;
AdjList.resize(n);
for(int i=0; i<m; i++){
cin >> p >> q >> r;
AdjList[p].push_back({q, r});
AdjList[q].push_back({p, r});
}
vi dist(n); dist.assign(n, inf); dist[s] = 0;
priority_queue< ii, vector<ii>, greater<ii> > pq; pq.push(ii(0, s));
while (!pq.empty()) {
ii front = pq.top(); pq.pop();
int d = front.first, u = front.second;
if (d > dist[u]) continue;
for (int j = 0; j < (int)AdjList[u].size(); j++) {
ii v = AdjList[u][j];
if (dist[u] + v.second < dist[v.first]) {
dist[v.first] = dist[u] + v.second;
pq.push(ii(dist[v.first], v.first));
}
}
}
cout << "Case #" << (cas++) << ": ";
if(dist[t] == inf) cout << "unreachable\n";
else cout << dist[t] << "\n";
}
return 0;
}