题意：n个点，给定每个点的层次，可以从当前层任何节点到达下一个层任何节点，x->x+1 ，x+1->x 花费c，还有一些额外的边可以直接走。求1-n的最短路
做法：想到了如果直接扩展所有节点的话肯定超时，所以找出关键点扩展就好了，什么关键点，叫着好听而已，就是那些必要的点而已，包括给出的边的点，还有起点终点，每层至少保证一个点。然后spfa迭代，按额外的边迭代，往上一层迭代，往下一层迭代。
刚开始没能保证n点加进去，一直wa
#define maxn 100005 const int inf = 0x3fffffff; struct node { int v,next; int w ; }; node e[maxn * 2 ]; int cnt ; int head[maxn]; vector<int> p[maxn],p1[maxn]; int vis[maxn]; int lev[maxn]; int n,m,c; int _mx; int dis[maxn]; void init() { memset(head,-1,sizeof(head)); cnt = 0 ; } void add(int u , int v , int w ) { //printf("add %d %d %d ",u,v,w); e[cnt].v = v ; e[cnt].w = w ; e[cnt].next = head[u] ; head[u] = cnt ++ ; e[cnt].v = u; e[cnt].w = w; e[cnt].next = head[v]; head[v] = cnt ++ ; return ; } queue<int> q; void spfa() { while(!q.empty()) q.pop(); for(int i = 0; i <= n ; i ++ ) { vis[i] = 0 ; dis[i] = inf; } vis[1] = 1 ; dis[1] = 0 ; q.push(1); int u , v , ll ,sz ; while(!q.empty()) { u = q.front(); // printf("u = %d lev[%d] = %d ",u,u,lev[u]); // printf("dis[u] = %d ",dis[u]); q.pop(); for(int i = head[u]; i != -1 ; i = e[i].next) { //printf("e[i].w = %d ",e[i].w); v = e[i].v; if(dis[u] + e[i].w < dis[v] ) { dis[v] = dis[u] + e[i].w ; // printf("dis[%d] = %d ",v,dis[v]); if(!vis[v] ) { vis[v] = 1 ; q.push(v); } } } ll = lev[u]; if(ll != 1 ) { sz = p1[ll-1].size(); for(int i = 0 ; i < sz; i ++ ) { v = p1[ll-1][i]; if(dis[u] + c < dis[v] ) { dis[v] = dis[u] + c ; if(!vis[v] ) { vis[v] = 1 ; q.push(v); } } } } if(ll != _mx) { sz = p1[ll+1].size(); for(int i = 0 ; i < sz; i ++ ) { v = p1[ll+1][i]; if(dis[u] + c < dis[v] ) { dis[v] = dis[u] + c ; // printf("dis[%d] = %d ",v,dis[v]); if(!vis[v] ) { vis[v] = 1 ; q.push(v); } } } } vis[u] = 0; } } int main() { int cas; int cast = 0 ; scanf("%d",&cas); while(cas -- ) { scanf("%d%d%d",&n,&m,&c); // printf("c = %d ",c); memset(lev, 0 , sizeof(lev)); for(int i = 1 ; i <= n; i ++ ) p[i].clear(),p1[i].clear(); memset(vis,0,sizeof(vis)); _mx = 0 ; for(int i = 1 ; i <= n ; i++ ) { scanf("%d",&lev[i]); _mx = max(_mx , lev[i]); p[lev[i]].push_back(i); if(p1[lev[i]].size() <= 3 ) { p1[lev[i]].push_back(i); vis[i] = 1 ; } } init(); int u,v,w; for(int i = 0; i < m ; i ++ ) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); if(!vis[u]) { p1[lev[u]].push_back(u); vis[u] = 1 ; } if(!vis[v] ) { p1[lev[v]].push_back(v); vis[v] = 1 ; } } if(n == 0 ) { printf("Case #%d: -1 ",++cast); continue; } else if(n == 1 ) { printf("Case #%d: 0 ",++cast); continue; } if(!vis[1])p1[lev[1]].push_back(1); if(!vis[n])p1[lev[n]].push_back(n); // for(int i = 1 ; i <= _mx; i ++ ) //{ // for(int j = 0 ; j < p1[i].size(); j ++ ) // { // printf("%d ",p1[i][j]); // } // printf(" "); // } spfa(); printf("Case #%d: ",++cast); if(dis[n] >= inf) printf("-1 "); else printf("%d ",dis[n]); } return 0; }