/*
*好险 968ms飘过。。。。。。。。。
*说说我的感受，刚开始就直接敲堆优化的dij...发现直接就TLE了，改了好多种建边的方法依然是超时，之后才想到这种方法：
*给每层建两个结点，分别标记为 n+2*i-1 和 n +2*i 。然后每个结点到它所在层结点的费用为0，第i层到第i+1层的费用为 C。
*当然由于是双向边，要保证相邻两层的结点都是互相可达的。
*/
1 #include<stdio.h> 2 3 #include<string.h> 4 #include<queue> 5 #include<vector> 6 using namespace std; 7 #define min(x,y) (x<y?x:y) 8 #define max(x,y) (x>y?x:y) 9 #define max_n 100010*3 10 #define inf 0x3f3f3f3f 11 12 int n,m,c; 13 struct Edge{ 14 int to,dist; 15 Edge(int t,int d):to(t),dist(d){} 16 }; 17 struct node{ 18 int d,u; 19 node(int dd,int uu):d(dd),u(uu){} 20 bool operator < (const node& tmp)const{ 21 return d>tmp.d; 22 } 23 }; 24 vector<int> next[max_n];//每个结点出发的边编号 25 vector<Edge> edges; //边列表 26 bool done[max_n]; //是否已永久标记 27 int d[max_n]; //1到各个点的距离 28 29 void init(int n){ 30 for(int i=1;i<=n*3;i++){ 31 next[i].clear();//清空临界表 32 } 33 edges.clear();//清空边表 34 } 35 36 void add_edge(int from,int to,int dist){ 37 //无向图需两次加边 38 edges.push_back(Edge(to,dist)); 39 int count=edges.size(); 40 next[from].push_back(count-1); 41 } 42 43 void dij(){ 44 memset(d,0x3f,sizeof(d)); 45 d[1]=0; 46 memset(done,false,sizeof(done)); 47 priority_queue<node> q; 48 q.push(node(0,1)); 49 while(!q.empty()){ 50 node x=q.top(); q.pop(); 51 int u=x.u; 52 if(done[u]){ 53 continue; 54 } 55 done[u]=true; 56 for(int i=0;i<next[u].size();i++){ 57 Edge& e=edges[next[u][i]]; 58 if(!done[e.to]&&d[e.to]>d[u]+e.dist){ 59 d[e.to]=d[u]+e.dist; 60 q.push(node(d[e.to],e.to)); 61 } 62 } 63 } 64 } 65 66 int main(){ 67 int T; 68 scanf("%d",&T); 69 for(int t=1;t<=T;t++){ 70 scanf("%d%d%d",&n,&m,&c); 71 init(n); 72 for(int i=1;i<=n;i++){ 73 int u; 74 scanf("%d",&u); 75 add_edge(i,n+2*u-1,0); 76 add_edge(n+2*u,i,0); 77 } 78 for(int i=1;i<n;i++){ 79 add_edge(n+2*i-1,n+2*(i+1),c); 80 add_edge(n+2*(i+1)-1,n+2*i,c); 81 } 82 for(int i=1;i<=m;i++){ 83 int u,v,w; 84 scanf("%d%d%d",&u,&v,&w); 85 add_edge(u,v,w); 86 add_edge(v,u,w); 87 } 88 dij(); 89 printf("Case #%d: ",t); 90 if(d[n]==inf){ 91 puts("-1"); 92 } 93 else{ 94 printf("%d ",d[n]); 95 } 96 } 97 }