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