题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4725
题目大意：有n层，n个点分布在这些层上，相邻层的点是可以联通的且距离为c，还有额外给出了m个条边，求1号点到n号点的最短距离，若无法到达则输出“-1”。
解题思路：最短路问题，主要是建图很难。如果按常规建法，用邻接表存每层的节点编号然后在建边肯定会超时，因为如果点只分布在两个层上，那建边的复杂度就是O（n^2）了。所以要改变一下思路，可以用n个虚拟点来代表n层，把连到该层的点都连接到虚拟点上，同一层花费为0，不同层花费为c。但是还需要一点处理，不然这样的话同一层的点的花费就会变成0，原本可能不可达的变得可达。这是我从别人博客看来的两种方法（出处）：
A.每层拆两个点，一个点管入，一个点管出，这样的话同层的点不会回到同层的另外一个点上。
B.每层拆一个点，这个点只管入，而处于该层的点则向左右两层虚拟点相连。
我用的是方法B，建了2n个点（有n个是虚拟点），边数大概为5n条（点和点2n，点和相邻层2n，虚拟点到同层的点n）
代码：
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+;
const int INF=0x3f3f3f3f; struct node{
int to,next,w;
}edge[*N]; int n;
int idx,head[N],dis[N],layer[N];//layer[i]记录第i个点所在的层
bool vis[N],sign[N];//sign[i]记录第i层是否有点 void init(){
idx=;
memset(head,-,sizeof(head));
} void addEdge(int u,int v,int w){
edge[idx].to=v;
edge[idx].w=w;
edge[idx].next=head[u];
head[u]=idx;
idx++;
} void spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty()){
int k=q.front();
q.pop();
vis[k]=false;
for(int i=head[k];i!=-;i=edge[i].next){
node t=edge[i];
if(dis[k]+t.w<dis[t.to]){
dis[t.to]=dis[k]+t.w;
if(!vis[t.to]){
q.push(t.to);
vis[t.to]=true;
}
}
}
}
} int main(){
int t,cas=;
scanf("%d",&t);
while(t--){
init();
memset(sign,false,sizeof(sign));
int m,c;
scanf("%d%d%d",&n,&m,&c);
for(int i=;i<=n;i++){
scanf("%d",&layer[i]);
sign[layer[i]]=true;
}
for(int i=;i<=n-;i++){ //相邻层的虚拟点建边
if(sign[i]&&sign[i+]){ //当两个相邻层都有点才建边
addEdge(i+n,i+n+,c);
addEdge(i+n+,i+n,c);
}
}
for(int i=;i<=n;i++){ //虚拟点到同一层的点建边
addEdge(layer[i]+n,i,);
if(layer[i]>) //点和相邻层的虚拟点建边
addEdge(i,layer[i]+n-,c);
if(layer[i]<n)
addEdge(i,layer[i]+n+,c);
} for(int i=;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
spfa();
if(dis[n]<INF)
printf("Case #%d: %d\n",++cas,dis[n]);
else
printf("Case #%d: -1\n",++cas);
}
return ;
}