题意：N个点，每个点有一个层号L，相邻的两层 Li 与 Li+1 之间的距离为C。另外给出M条无向边，求从点1到点N的最短路。
分析：同一层之间的两点距离并不是0，这是一个小坑。依次把相邻两层的所有点连边会导致复杂度很高。可以将每一层看作一个点，但是把它和层中的点连边会导致同层的两点距离为0。
为了避免这种情况，可以将每层拆作两点，表示入点和出点。所以所建图中一共有3N个点。1~N为原图中的点，N+1~2*N为每层出点，2*N+1~3*N为每层入点。对每个在该层中的点u，将其连至出点N+i；再将入点2N+i连至u。再将相邻两层的出点入点对应连接。最后跑一下Dijkstra。
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn = 3e5+5;
const LL INF = 1ll<<60;
struct Edge{int to,next;LL val;
};
struct HeapNode{LL d; //费用或路径int u;bool operator < (const HeapNode & rhs) const{return d > rhs.d;}
};
struct Dijstra{int n,m,tot;Edge edges[maxn<<4];bool used[maxn];LL d[maxn];int head[maxn];void init(int n){this->n = n;this->tot=0;memset(head,-1,sizeof(head));}void Addedge(int u,int v ,LL dist){edges[tot].to = v;edges[tot].val = dist;edges[tot].next = head[u];head[u] = tot++;}void dijkstra(int s){ memset(used,0,sizeof(used));priority_queue<HeapNode> Q;for(int i=0;i<=n;++i) d[i]=INF;d[s]=0;Q.push((HeapNode){0,s});while(!Q.empty()){HeapNode x =Q.top();Q.pop();int u =x.u;if(used[u]) continue;used[u]= true;for(int i=head[u];~i;i=edges[i].next){Edge & e = edges[i];if(d[e.to] > d[u] + e.val){d[e.to] = d[u] +e.val;Q.push((HeapNode){d[e.to],e.to});}}}}
}G;int lay[maxn];//#define LOCAL
int main()
{#ifdef LOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint N,M,T,u,v,cas=1;LL tmp,C;scanf("%d",&T);while(T--){scanf("%d%d%lld",&N,&M,&C);G.init(3*N);for(int i=1;i<=N;++i){scanf("%d",&tmp);G.Addedge(i,tmp+N,0); //1~N为层,N~2*N为出点，2*N~3*N为入点G.Addedge(tmp+2*N,i,0);}for(int i=1;i<=N-1;++i){G.Addedge(N+i,2*N+i+1,C); //将相邻两层出点入点对应连接G.Addedge(N+i+1,2*N+i,C);}for(int i=1;i<=M;++i){scanf("%d%d%lld",&u,&v,&tmp);G.Addedge(u,v,tmp);G.Addedge(v,u,tmp);}G.dijkstra(1);if(G.d[N]==INF) G.d[N]=-1;printf("Case #%d: %lld\n",cas++,G.d[N]);} return 0;
}