最短路问题，主要考的是构图的思想；
思路：
将每一层拆分成两个点，例如，第一层分成n+1即(n+2*i-1)和n+2(n+2*i)；总共3*n个点；
也就是第i层分成n+2*i-1和n+2*i;规定n+2*i-1始终作为入边，n+2*i始终作为出边;
如果某个点属于第i层，就连边i->n+2*i-1,n+2*i->i，权值为0;
然后根据题意，相邻的层次连边，权值为C，n+2*i-1->n+2*(i+1)和n+2*(i+1)-1->n+2*i;
然后跟着输入的边构图；
#include<cstdlib> #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define inf 0x7fffffff #define eps 1e-7 #define N 100005*3 using namespace std; typedef pair<int,int> pii; int m,n,T,t,c; vector<pii >g[N]; int d[N],vis[N]; void init() { for (int i=0; i<=3*n; ++i ) { g[i].clear(); } memset(vis,0,sizeof(vis)); } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif scanf("%d",&T); int ncase=0; while(T--) { scanf("%d%d%d",&n,&m,&c); init(); for (int i=1; i<=n; ++i ) { scanf("%d",&t); if(i!=1) g[n+i*2-1].push_back(make_pair(n+(i-1)*2,c));//层的内部 if(i!=n) g[n+i*2-1].push_back(make_pair(n+(i+1)*2,c)); g[i].push_back(make_pair(n+t*2-1,0));//层的外部 g[n+t*2].push_back(make_pair(i,0)); } while(m--) { int x,y,z; scanf("%d%d%d",&x,&y,&z); g[x].push_back(make_pair(y,z)); g[y].push_back(make_pair(x,z)); } priority_queue<pii,vector<pii >,greater<pii > >q; q.push(make_pair(0,1)); int ok=0; while(!q.empty()) { pii p=q.top(); q.pop(); int u=p.second; if(vis[u])//////////////// continue; int len=p.first; vis[u]=1; d[u]=len; if(u==n) { ok=1; break; } for(int i=0; i<g[u].size(); i++) { int v=g[u][i].first; if(!vis[v]) { q.push(make_pair(len+g[u][i].second,v)); } } } // for (int i=1; i<=n; ++i ) // cout<<"##d[i]="<<d[i]<<endl; printf("Case #%d: %d ",++ncase,ok?d[n]:-1); } return 0; }