题目：http://acm.split.hdu.edu.cn/showproblem.php?pid=4725
题意：有N个点和N层，一层有X个点(0<=X<=N)，两邻层间有一条路花费C，即该层到邻层上的任意点距离为C，同层间的点距离不是0，除非存在后面讲的小路贯通。还有M条小路在两个点之间。问从第一个点走到第N个点最短路是多少。输入说明：先输入测试数据的数量，在输入N M C，接下来一行输入N个点所在的层数，再接下来输入M行，表示M行小路（无方向）。
题解：将i层拆成两个点，一个点（N+2×i-1）对于本层的点来说只进不出，并且同层点到该点距离为0，但对于邻层来说只出不进，另一个点（N+2×i）对于本层的点来说只出不进，并且到本层任意点距离为0，但对邻层来说只进不出，这样保证了同层无法通过这两个点到达本层的点，而邻层点可以通过该两点到达邻层任意点，并且花费只有C,对于输入的N个点所在层数，每次建立i-->（N+2×i-1）的距离为0的一条边和（N+2×i）---->i的距离为0的一条边，
建完之后建立两邻层的关系，即建立（N+2×i-1）---->（N+2×（i+1））距离为C和（N+2×（i+1）-1）---->（N+2×（i））距离为C；这样做保证了每次循环时i层的点都可以到达N+2×i-1，并可以通过此点到达邻层的N+2×（i+1）或N+2×（i-1），再通过这些点的0中转到达该层的任意点，注意时间复杂度和内存，最少保证有30w的点可以存下
代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#define MAX 300050
#define M 0x3f3f3f3f
using namespace std;
struct Edge
{
int e;
int w;
Edge(int _e=0,int _w=0):e(_e),w(_w){}
};
vector<Edge> head[MAX];
bool vis[MAX];
int dist[MAX];
struct qnode
{
int v;
int c;
qnode(int _v=0,int _c=0):v(_v),c(_c){}
bool operator <(const qnode &r)const
{
return c>r.c;
}
};
//o（eloge）
void Dijkstra(int n,int start)//点的编号从1开始
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)dist[i]=M;
priority_queue<qnode>que;
while(!que.empty())que.pop();
dist[start]=0;
que.push(qnode(start,0));
qnode tmp;
while(!que.empty())
{
tmp=que.top();
que.pop();
int u=tmp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<head[u].size();i++)
{
int v=head[u][i].e;
int cost=head[u][i].w;
if(!vis[v]&&dist[v]>dist[u]+cost)
{
dist[v]=dist[u]+cost;
que.push(qnode(v,dist[v]));
}
}
}
}
//o(e) 超时
void spfa(int start,int n)
{
queue<int> q;
q.push(start);
for(int i=1;i<=n;i++){dist[i]=M;vis[i]=false;}
dist[start]=0;
while(!q.empty())
{
int h=q.front();q.pop();
for(int i=0;i<head[h].size();i++)
{
Edge& p=head[h][i];
if(p.w+dist[h]<dist[p.e])
{
dist[p.e]=p.w+dist[h];
if(!vis[p.e]){q.push(p.e);vis[p.e]=true;}
}
}
vis[h]=false;
}
}
void addEdge(int s,int ed,int w)
{
head[s].push_back(Edge(ed,w));
}
int main()
{
int op=1;
int t;
scanf("%d",&t);
while(t--)
{
int n,m,c;
scanf("%d %d %d",&n,&m,&c);
int now;
for(int i=1;i<=n;i++) //输入第i点所在的层数，
{
scanf("%d",&now);
addEdge(i,n+now*2-1,0);
addEdge(n+now*2,i,0);
}
for(int i=1;i<n;i++)
{
addEdge(n+i*2-1,n+2*(i+1),c);
addEdge(n+2*(i+1)-1,n+2*i,c);
}
for(int i=1;i<=m;i++)
{
int s,ed,w;
scanf("%d %d %d",&s,&ed,&w);
addEdge(s,ed,w);
addEdge(ed,s,w);
}
//spfa(1,n*3);
Dijkstra(n*3,1);
if(dist[n]>=M)printf("Case #%d: -1\n",op++);
else printf("Case #%d: %d\n",op++,dist[n]);
for(int i=1;i<=3*n;i++) {head[i].clear();}
}
return 0;
}