典型的最短路问题，但是多了一个条件，就是每个点属于一个layer,相邻的layer移动，如x层移到x+1层需要花费c.
一种显而易见的转化是我把这些边都建出来，但是最后可能会使得边变成O(n^2);
网上看到的一些做法就是拆点，假如我给每层做一个平台点，所有点都可以到这个平台，然后再换乘到别的平台里不就可以了吗？ 所以对于属于第i层的点我们构造一个i层点的虚拟点，把这些点连到这个平台点，花费为0，相邻平台点之间的花费为c不就可以了吗？ 但是问题就出现在这里了，这样的话同一层的点的花费就会变成0，原本可能不可达的变得可达。网上看到的拆点方法有这么两种。
A.每层拆两个点，一个点管入，一个点管出，这样的话同层的点不会回到同层的另外一个点上。
B.每层拆一个点，这个点只管入，而处于该层的点则向左右两层点相连。
A的话新建了2n个点，4n条边（两层相邻2n,每个点对应两条边2n,2n+2n＝4n），B的话新建了n个点，5n条边（平台间2n条，每个点2n条，平台到点n条）。
不知道上面有没算错请指正。具体参考了下面的博客：
http://www.baidu.com/link?url=MV7krOHUY-l_IgU1_R5qKyUVgL5ZRprWE1IznI82Vwoo_RG_LrIaqxvCJismujP2TVaEEFg607BdhwWeUEy5aa
http://www.cnblogs.com/kuangbin/archive/2013/09/11/3315071.html
这道题当作是SPFA的模板练习题吧，晚了，睡觉去～
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define maxn 300150
#define maxm 700100
#define inf 0x3f3f3f3f
using namespace std;
int first[maxn];
int nxt[maxm];
int e;
int vv[maxm];
int cost[maxm];
int n, m, c;
int layer[maxn];
int dis[maxn];
bool in[maxn];
void addedge(int u, int v, int w)
{
vv[e] = v; cost[e] = w;
nxt[e] = first[u];
first[u] = e++;
}
void spfa(int s)
{
queue<int> q;
memset(in, 0, sizeof(in));
memset(dis, 0x3f, sizeof(dis));
q.push(s); dis[s] = 0; in[s] = true;
while (!q.empty()){
int u = q.front(); q.pop();
in[u] = false;
for (int i = first[u]; i != -1; i=nxt[i]){
int v = vv[i];
if (dis[v] > dis[u] + cost[i]){
dis[v] = dis[u] + cost[i];
if (!in[v]) q.push(v), in[v] = true;
}
}
}
}
int vlayer[maxn];
int main()
{
int T; cin >> T; int ca = 0;
while (T--)
{
e = 0; memset(first, -1, sizeof(first));
memset(vlayer, 0, sizeof(vlayer));
scanf("%d%d%d", &n, &m, &c);
for (int i = 1; i <= n; i++){
scanf("%d", layer + i);
vlayer[layer[i]] = 1;
}
for (int i = 1; i <= n-1; i++){
if (vlayer[i] && vlayer[i + 1]){
addedge(n + i, n + i + 1, c);
addedge(n + i + 1, n + i, c);
}
}
for (int i = 1; i <= n; i++){
addedge(n + layer[i], i, 0);
if (layer[i] > 1) addedge(i, n+layer[i] - 1, c);
if (layer[i] < n) addedge(i, n+layer[i] + 1, c);
}
int ui, vi, wi;
for (int i = 0; i < m; i++){
scanf("%d%d%d", &ui, &vi, &wi);
addedge(ui, vi, wi);
addedge(vi, ui, wi);
}
spfa(1);
int ans = dis[n];
if (ans<inf) printf("Case #%d: %d
",++ca, dis[n]);
else printf("Case #%d: %d
", ++ca, -1);
}
return 0;
}