题意：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#include #include #include #include #include #include #include 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 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 LOCALint main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int 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;}