HDU-4725.TheShortestPathinNyaGraph(最短路 + 建图)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 const int maxn = 5e5, INF = 0x3f3f3f3f;
 7 int n, m, c, Case = 1, num;
 8 int dist[maxn], layer[maxn], head[maxn];
 9 struct node {
10     int to, cost, Next;
11 } edge[maxn];
12 bool vis[maxn];
13 
14 void addedge(int u, int v, int w) {
15     edge[num].to = v;
16     edge[num].Next = head[u];
17     edge[num].cost = w;
18     head[u] = num ++;
19 }
20 
21 // void Spfa() {
22 //     for(int i = 1; i <= num; i ++)
23 //         dist[i] = (i == 1 ? 0 : INF);
24 //     memset(vis, false, sizeof vis);
25 //     queue <int> Q;
26 //     Q.push(1);
27 //     vis[1] = true;
28 //     while(!Q.empty()) {
29 //         int u = Q.front();
30 //         Q.pop();
31 //         for(int k = head[u]; k != - 1; k = edge[k].Next) {
32 //             int v = edge[k].to;
33 //             if(dist[v] > dist[u] + edge[k].cost) {
34 //                 dist[v] = dist[u] + edge[k].cost;
35 //                 if(!vis[v])Q.push(v);
36 //             }
37 //         }
38 //     }
39 // }
40 
41 struct Rule {
42     bool operator () (int a,int b) const {
43         return dist[a] > dist[b];
44     }
45 };
46 void dijkstra(int s) {
47     fill(dist, dist + num, INF);
48     priority_queue<int, vector<int>, Rule> q;
49     dist[s] = 0;
50     q.push(s);
51     while(!q.empty()) {
52         int u = q.top(); q.pop();
53         for(int k = head[u]; k != -1; k = edge[k].Next) {
54             int v = edge[k].to;
55             if(dist[v] > dist[u] + edge[k].cost) {
56                 dist[v] = dist[u] + edge[k].cost;
57                 q.push(v);
58             }
59             
60         }
61     }
62 }
63 
64 int main () {
65     int t, u, v, cost;
66     scanf("%d", &t);
67     while(t --) {
68         scanf("%d %d %d", &n, &m, &c);
69         num = 0;
70         memset(head, -1, sizeof head);
71         memset(layer, 0, sizeof layer);
72         for(int i = 1; i <= n; i ++) {
73             scanf("%d", &u);
74             layer[i] = u;
75             addedge(i, n + 2 * u - 1, 0);
76             addedge(n + 2 * u, i, 0);
77             vis[u] = true;
78         }
79         for(int i = 1; i < n; i ++) {
80             if(vis[i] && vis[i + 1]) {
81                 addedge(n + 2 * i - 1, n + 2 * (i + 1), c);
82                 addedge(n + 2 * (i + 1) - 1, n + 2 * i, c);
83             }
84         }
85         for(int i = 0; i < m; i ++) {
86             scanf("%d %d %d", &u, &v, &cost);
87             addedge(u, v, cost);
88             addedge(v, u, cost);
89         }
90         // Spfa();
91         dijkstra(1);
92         if(dist[n] == INF || n == 0)
93             printf("Case #%d: -1\n", Case++);
94         else
95             printf("Case #%d: %d\n", Case++, dist[n]);
96     }
97     return 0;
98 }