LightOJ - 1019 - Brush (V)

1. #include <bits/stdc++.h>
2. #define C 103
3. #define MX 1000000000
4. using namespace std;
5.  
6. vector <int> Junction[C], cost[C];
7. int dist[C];
8.  
9. struct data{
10.     int source, weight;
11.     data(int x, int y){
12.         source = x, weight = y;
13.     }
14.     bool operator < (const data& p)const{
15.         weight < p.weight;
16.     }
17. };
18.  
19. void dijkstra(int n, int src){
20.     for(int i = 0; i <= n; i++)dist[i] = MX;
21.     dist[src] = 0;
22.     priority_queue <data> Q;
23.     Q.push(data(src, 0));
24.     while(!Q.empty()){
25.         data top = Q.top();
26.         int u = top.source;
27.         Q.pop();
28.         int sz = Junction[u].size();
29.         for(int i = 0; i < sz; i++){
30.             int v = Junction[u][i];
31.             if(dist[u]+cost[u][i] < dist[v]){
32.                 dist[v] = dist[u]+cost[u][i];
33.                 Q.push(data(v, dist[v]));
34.             }
35.         }
36.     }
37.     if(dist[n] == MX)puts("Impossible");
38.     else printf("%d\n", dist[n]);
39. }
40.  
41. int main(){
42.     int n, m, t, u, v, w, cs = 0;
43.     scanf("%d", &t);
44.     while(t--){
45.         scanf("%d %d", &n, &m);
46.         for(int i = 0; i < m; i++){
47.             scanf("%d %d %d", &u, &v, &w);
48.             cost[u].push_back(w);
49.             cost[v].push_back(w);
50.             Junction[u].push_back(v);
51.             Junction[v].push_back(u);
52.         }
53.         printf("Case %d: ", ++cs);
54.         dijkstra(n, 1);
55.         for(int i = 0; i < C; i++)Junction[i].clear(), cost[i].clear();
56.     }
57.     return 0;
58. }