本题思路：主要是建图比较麻烦，因为结点可以在层与层之间走动，也可以在边上进行走动，所以主要就是需要找到一个将结点和层统一化处理的方法。
所以我们就可以对于存在边的结点建边，层与层之间如果层数相差一也建一条权值为c的边，相同层数之间的也建一条权值为零的边，接着Dijkstra即可。
参考代码：spfa超时了，所以就改成了Dijkstra。
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 ", Case++); 94 else 95 printf("Case #%d: %d ", Case++, dist[n]); 96 } 97 return 0; 98 }