题目链接:传送门
题目大意:首先输入n,m,c；n代表点数，m是额外的边，c是层与层之间的权值。然后接下来n个数分别表示第i个点属于哪个层（层与层之间可互通），然后m行，每行三个数 x，y，v，表示点x到y权值为v求点1到点n的最短路。
题目思路:把每个层拆成两个点（点到相应层之间距离为0），注意是拆成两个点，原因很简单，如果只拆成一个点，那么如果点1属于1层，点2也属于1层，那么推出来1与2距离为0， 结果错误，所以拆成两个点，前一个点代表入点（点到层），都一个代表出点（层到点），然后SPFA或者堆优化dijkstra就行。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define seg int root,int l,int r #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define Min(x,y) (x<y?x:y) #define Max(x,y) (x>y?x:y) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 1000001 #define maxn 300021 typedef long long LL; typedef pair<int,int> PII; int vis[maxn],d[maxn],head[maxn],n,m,ans; int a[maxn]; struct Node{ int to,next,v; Node(){} Node(int a,int b,int c):to(a),next(b),v(c){} }node[N];int hcnt=0; void add(int x,int y,int v){ ///加边 node[hcnt]=Node(y,head[x],v); head[x]=hcnt++; } void spfa(){ mst(d,inf); d[1]=0; mst(vis,0); vis[1]=1; deque<int>q; ///deque优化 q.push_back(1); while(!q.empty()){ int s=q.front();q.pop_front(); vis[s]=0; for(int i=head[s];~i;i=node[i].next){ int e=node[i].to; if(d[e]>d[s]+node[i].v){ d[e]=d[s]+node[i].v; if(!vis[e]){ if(!q.empty()&&d[e]<d[q.front()]) q.push_front(e); else q.push_back(e); vis[e]=1; } } } } if(d[n]==inf) ans=-1; else ans=d[n]; } int main(){ int i,j,group,x,y,v,Case=0; scanf("%d",&group); while(group--){ mst(head,-1); hcnt=0; scanf("%d%d%d",&n,&m,&v); for(i=1;i<=n;++i){ scanf("%d",&x); add(i,n+2*x-1,0); ///加入边 add(n+2*x,i,0); ///加出边 } for(i=1;i<n;++i){ add(n+2*i-1,n+2*(i+1),v); ///注意合并顺序，入边与出边相对应 add(n+2*(i+1)-1,n+2*i,v); ///这样才能避免同一层的点距离为0的情况 } while(m--){ scanf("%d%d%d",&x,&y,&v); add(x,y,v); add(y,x,v); } spfa(); printf("Case #%d: %d ",++Case,ans); } return 0; }