HDU4725TheShortestPathinNyaGraph（最短路径）（2013ACM/ICPCAsiaRegionalOnline――Warmup2）

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 using namespace std;
 7 typedef pair<int, int> PII;
 8 
 9 const int MAXN = 300010;
10 const int MAXE = MAXN * 2;
11 
12 int head[MAXN];
13 int to[MAXE], next[MAXE], cost[MAXE];
14 int n, m, ecnt, lcnt, c;
15 
16 void init() {
17     memset(head, 0, sizeof(head));
18     ecnt = lcnt = 1;
19 }
20 
21 inline void add_edge(int u, int v, int c) {
22     to[ecnt] = v; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
23 }
24 
25 int dis[MAXN];
26 int lay[MAXN];
27 bool vis[MAXN];
28 
29 void Dijkstra(int st, int ed) {
30     memset(dis, 0x7f, sizeof(dis));
31     memset(vis, 0, sizeof(vis));
32     priority_queue que; que.push(make_pair(0, st));
33     dis[st] = 0;
34     while(!que.empty()) {
35         int u = que.top().second; que.pop();
36         if(vis[u]) continue;
37         if(u == ed) return ;
38         vis[u] = true;
39         for(int p = head[u]; p; p = next[p]) {
40             int &v = to[p];
41             if(dis[v] > dis[u] + cost[p]) {
42                 dis[v] = dis[u] + cost[p];
43                 que.push(make_pair(-dis[v], v));
44             }
45         }
46     }
47 }
48 
49 int T;
50 
51 inline int readint() {
52     char c = getchar();
53     while(!isdigit(c)) c = getchar();
54     int ret = 0;
55     while(isdigit(c)) ret = ret * 10 + c - '0', c = getchar();
56     return ret;
57 }
58 
59 int main() {
60     T = readint();
61     for(int t = 1; t <= T; ++t) {
62         n = readint(), m = readint(), c = readint();
63         init();
64         for(int i = 1; i <= n; ++i) {
65             lay[i] = readint();
66             add_edge(i, n + 2 * lay[i] - 1, 0);
67             add_edge(n + 2 * lay[i], i, 0);
68         }
69         for(int i = 1; i i) {
70             add_edge(n + 2 * i - 1, n + 2 * (i + 1), c);
71             add_edge(n + 2 * (i + 1) - 1, n + 2 * i, c);
72         }
73         int u, v, w;
74         while(m--) {
75             //scanf("%d%d%d", &u, &v, &w);
76             u = readint(), v = readint(), w = readint();
77             add_edge(u, v, w);
78             add_edge(v, u, w);
79         }
80         Dijkstra(1, n);
81         if(dis[n] == 0x7f7f7f7f) dis[n] = -1;
82         printf("Case #%d: %d\n", t, dis[n]);
83     }
84 }