<题目链接>
题目大意：
每个点放在一层，然后给了n个点，相邻的两层距离是固定的c，有额外m条无向边，然后求1到n的最短路径，如果没有则输出-1 。
解题分析：
本题建图是关键，需要注意的是，每一层不一定只有一个点。因此，如果两层之间建边时只是简单将上面的所有点的相互连接，那么取极端情况，当只有两层
并且每层只有50000个点时，在O(N^2)的复杂度下，光是建图就已经爆了。所以我们对每一层进行拆点，但是如果每一层只拆成一个点的话，那么该层每一个
点与拆成的点之间是双向边，这样的话，该层之间所有的点之间的距离就为0了，明显不符合题意。所以我们每一层要拆成两个点，该层所有点----->拆点1，
拆点2----->该层所有点，这样该层所有点之间就不是相互可达了。
#include <bits/stdc++.h> using namespace std; const int M = 8e5+10; #define INF 0x3f3f3f3f int n,m,c; struct EDGE{ int to,val,nxt; }dge[M]; int head[M],cnt; int vis[M]; struct NODE{ int loc,dis; bool operator <(const NODE &tmp)const{ return dis>tmp.dis; } }d[M]; inline void init(){ cnt=0;memset(head,-1,sizeof(head)); } inline void add(int u,int v,int w){ e[cnt]=(Edge){v,w,head[u]};head[u]=cnt++; } void dij(int N){ for(int i=1;i<=N;i++){ vis[i]=0; d[i].loc=i,d[i].dis=INF; } priority_queue<NODE>q; d[1].dis=0; q.push(d[1]); while(!q.empty()){ NODE now=q.top(); q.pop(); if(vis[now.loc])continue; vis[now.loc]=1; for(int i=head[now.loc];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(d[v].dis>d[now.loc].dis+edge[i].val){ d[v].dis=d[now.loc].dis+edge[i].val; q.push(d[v]); } } } } int main(){ int ncase=0; int T;scanf("%d",&T); while(T--){ init(); scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=n;i++){ int u;scanf("%d",&u); add(i,n+2*u-1,0); //如果只将每一层虚拟成一个点，那么这样建双向边的话，就会使每一层的点相互可达，并且权值为0，很明显不行 add(n+2*u,i,0); //所以要像这样，该层所有点指向N+2*u-1，N+2*u指向该层所有点，这样建图不会让该层所有点之间存在双向边，符合题意 } for(int i=1;i<n;i++){ add(n+2*i-1,n+2*(i+1),c); //连接i--->j层,让第i层管入度的虚拟点变成建边的起始点(把图想象出来就很好理解了) add(n+2*(i+1)-1,n+2*i,c); //连接j--->i层 } for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } dij(3*n); if(d[n].dis==INF)d[n].dis=-1; printf("Case #%d: %d ",++ncase,d[n].dis); } }
2018-09-02