思路：将每个layer拆成两个点，编号为N+x，和N+N+x。对所有属于layer x的点i,建N+x到i的有向边，在建i到N+N+x的有向边。最后对所有x号layer和x+1建一条N+N+x到N+x+1的有向边和一条N+N+x+1到N+x的有向边。
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define Maxn 300010
#define Maxm 80002
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 1000000000
#define lowbit(x) (x&(-x))
#define clr(x,y) memset(x,y,sizeof(x))
#define Mod 1000000007
using namespace std;
int head[Maxn],vi[Maxn],e,n,m,c;
int dis[Maxn];
struct Edge{
int u,v,next;
int val;
}edge[Maxn*];
struct Point{
int id;
Point (int a){id=a;}
int operator<(const Point &temp) const{
return dis[id]>dis[temp.id];
}
};
priority_queue<Point> q;
void init()
{
memset(head,-,sizeof(head));
memset(vi,,sizeof(vi));
e=;
}
void add(int u,int v,int val)
{
edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++;
}
void spfa()
{
int i,j,v,now;
for(i=;i<Maxn;i++)
dis[i]=inf;
dis[]=;
memset(vi,,sizeof(vi));
Point p();
while(!q.empty())
q.pop();
q.push();
while(!q.empty()){
p=q.top();
now=p.id;
q.pop();
if(now==n)
return ;
vi[now]=;
for(i=head[now];i!=-;i=edge[i].next){
v=edge[i].v;
if(dis[now]+edge[i].val<dis[v]){
dis[v]=dis[now]+edge[i].val;
if(!vi[v]){
vi[v]=;
q.push(v);
}
}
}
}
}
int main()
{
int t,i,j,u,v,val,x,Case=;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d%d",&n,&m,&c);
for(i=;i<=n;i++){
scanf("%d",&x);
add(n+x,i,);
add(i,*n+x,);
vi[x]=;
}
for(i=;i<n;i++){
if(vi[i]&&vi[i+]){
add(*n+i,n+i+,c);
add(*n+i+,n+i,c);
}
}
for(i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&val);
add(u,v,val);
add(v,u,val);
}
if(n==){
printf("Case #%d: -1\n",++Case);
continue;
}
spfa();
printf("Case #%d: ",++Case);
if(dis[n]>=inf)
printf("-1\n");
else
printf("%d\n",dis[n]);
}
return ;
}