我们根据每个人的layer把相同layer的人分配到同一个层次中。
然后记录走到每个层次的最小值。如果这个最小值被更新了， 那么我们就更新与这个层次相连的层次上的点。
其他的就是最普通的spfa求最短路了。
不过要用优先队列优化一下。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define maxn 110000
#define INF 99999999
struct list
{int next;int u,v,w;
} edge[maxn*2];
vector<int>vec[maxn];
struct listt
{int u;int w;friend bool operator <(const listt &a,const listt &b){return a.w>b.w;}
} p,q;
priority_queue<struct listt>que;
int head[maxn];
int nums;
map<int,int>mp;
void init()
{for(int i=0; i<maxn; i++)vec[i].clear();memset(head,-1,sizeof(head));nums=1;while(!que.empty())que.pop();mp.clear();
}
void add(int u,int v,int w)
{edge[nums].u=u;edge[nums].v=v;edge[nums].w=w;edge[nums].next=head[u];head[u]=nums++;
}
int dis[maxn];
int minn[maxn];
int belong[maxn];
int ans[maxn];
int spfa(int st,int ed,int k)
{for(int i=0; i<=ed; i++)dis[i]=INF;for(int i=0; i<=maxn; i++)minn[i]=INF;p.u=st;p.w=0;que.push(p);dis[st]=0;while(!que.empty()){q=que.top();que.pop();if(q.u==ed){return q.w;}int x=belong[q.u];if(q.w<minn[x]){minn[x]=q.w;p.w=minn[x]+k;if(ans[x-1]+1==ans[x]){for(int i=0; i<vec[x-1].size(); i++){p.u=vec[x-1][i];if(dis[p.u]>p.w){dis[p.u]=p.w;que.push(p);}}}if(ans[x]+1==ans[x+1]){for(int i=0; i<vec[x+1].size(); i++){p.u=vec[x+1][i];if(dis[p.u]>p.w){dis[p.u]=p.w;que.push(p);}}}}for(int i=head[q.u]; i!=-1; i=edge[i].next){int v=edge[i].v;int w=edge[i].w;if(dis[v]>dis[q.u]+w){dis[v]=dis[q.u]+w;p.u=v;p.w=dis[v];que.push(p);}}}return -1;
}
vector<int>all;
int main()
{int cas=0;int T,m,n,k,u,v,w;scanf("%d",&T);while(T--){cas++;init();scanf("%d%d%d",&n,&m,&k);all.clear();for(int i=1; i<=n; i++){scanf("%d",&belong[i]);//vec[belong[i]].push_back(i);all.push_back(belong[i]);}//-----离散化sort(all.begin(),all.end());int st=1;mp[all[0]]=1;ans[1]=all[0];for(int i=1; i<all.size(); i++){if(all[i]!=all[i-1]){mp[all[i]]=++st;ans[st]=all[i];}}//-------------------for(int i=1; i<=n; i++){int x=mp[belong[i]];vec[x].push_back(i);belong[i]=x;}for(int i=1; i<=m; i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}printf("Case #%d: %d\n",cas,spfa(1,n,k));}return 0;
}