本题思路：主要是建图比较麻烦，因为结点可以在层与层之间走动，也可以在边上进行走动，所以主要就是需要找到一个将结点和层统一化处理的方法。
所以我们就可以对于存在边的结点建边，层与层之间如果层数相差一也建一条权值为c的边，相同层数之间的也建一条权值为零的边，接着Dijkstra即可。
参考代码：spfa超时了，所以就改成了Dijkstra。
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int maxn = 5e5, INF = 0x3f3f3f3f;
int n, m, c, Case = , num;
int dist[maxn], layer[maxn], head[maxn];
struct node {
int to, cost, Next;
} edge[maxn];
bool vis[maxn]; void addedge(int u, int v, int w) {
edge[num].to = v;
edge[num].Next = head[u];
edge[num].cost = w;
head[u] = num ++;
} // void Spfa() {
// for(int i = 1; i <= num; i ++)
// dist[i] = (i == 1 ? 0 : INF);
// memset(vis, false, sizeof vis);
// queue <int> Q;
// Q.push(1);
// vis[1] = true;
// while(!Q.empty()) {
// int u = Q.front();
// Q.pop();
// for(int k = head[u]; k != - 1; k = edge[k].Next) {
// int v = edge[k].to;
// if(dist[v] > dist[u] + edge[k].cost) {
// dist[v] = dist[u] + edge[k].cost;
// if(!vis[v])Q.push(v);
// }
// }
// }
// } struct Rule {
bool operator () (int a,int b) const {
return dist[a] > dist[b];
}
};
void dijkstra(int s) {
fill(dist, dist + num, INF);
priority_queue<int, vector<int>, Rule> q;
dist[s] = ;
q.push(s);
while(!q.empty()) {
int u = q.top(); q.pop();
for(int k = head[u]; k != -; k = edge[k].Next) {
int v = edge[k].to;
if(dist[v] > dist[u] + edge[k].cost) {
dist[v] = dist[u] + edge[k].cost;
q.push(v);
} }
}
} int main () {
int t, u, v, cost;
scanf("%d", &t);
while(t --) {
scanf("%d %d %d", &n, &m, &c);
num = ;
memset(head, -, sizeof head);
memset(layer, , sizeof layer);
for(int i = ; i <= n; i ++) {
scanf("%d", &u);
layer[i] = u;
addedge(i, n + * u - , );
addedge(n + * u, i, );
vis[u] = true;
}
for(int i = ; i < n; i ++) {
if(vis[i] && vis[i + ]) {
addedge(n + * i - , n + * (i + ), c);
addedge(n + * (i + ) - , n + * i, c);
}
}
for(int i = ; i < m; i ++) {
scanf("%d %d %d", &u, &v, &cost);
addedge(u, v, cost);
addedge(v, u, cost);
}
// Spfa();
dijkstra();
if(dist[n] == INF || n == )
printf("Case #%d: -1\n", Case++);
else
printf("Case #%d: %d\n", Case++, dist[n]);
}
return ;
}