题意：
给定n个点，每个点有一个坐标，坐标相差1的点两两之间有一条花费为c的路径，此外还有m条额外的双向边。求1到n的最短路径长度。
题目：
题意很裸，但是如果直接按题意建图，相邻坐标的边数最坏情况下高达，因此考虑怎么通过增加虚拟节点，在不改变题目要求的情况下减少边的数量。
首先，只有相邻两个坐标都有至少一个点时才有必要连边。
对于这样的相邻两个坐标x和x+1，可以创建两个虚拟结点x+n和x+n+n-1（当然第二个节点也可以是x+2*n，确保不冲突即可）。
然后将坐标为x的所有点向x+n连一条花费为c的边，x+n向所有坐标为x+1的点连一条花费为0的边。
坐标为x+1的所有点向x+2*n-1连一条花费为c的边，x+2*n-1向所有坐标为x的点连一条花费为0的边。
这样就保证了相邻坐标两两之间有了花费为c的路径，这样的边数至多为2*n（每个点有一条出边和一条入边）。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (root<<1)
#define rs ((root<<1)|1)
#define mst(a,b) memset(a,b,sizeof(a))
const int MAXN=3e5+5;
const int MAXM=1e5+5;
const db eps=1e-8;
const int INF=0x7f7f7f7f;
const int mod=1e9+7;
const int seed=131;
int t,n,m,c,id[MAXM];
struct Edge{int v,w;Edge(int _v=0,int _w=0):v(_v),w(_w){}bool operator<(const Edge &p)const{return w>p.w;}
};
vector<Edge> G[MAXN];
vector<int> e[MAXM];
int dis[MAXN];
bool vis[MAXN];
priority_queue<Edge> pq;
void dij(){mst(vis,0);mst(dis,INF);pq.push(Edge(1,0));dis[1]=0;while(!pq.empty()){int u=pq.top().v;pq.pop();if(vis[u]) continue;vis[u]=1;for(Edge tt:G[u]){int v=tt.v,w=tt.w;if(vis[v]) continue;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;pq.push(Edge(v,dis[v]));}}}
}
int main(){
// freopen("in.txt","r",stdin);scanf("%d",&t);For(cas,1,t){scanf("%d %d %d",&n,&m,&c);For(i,1,3*n) G[i].clear();For(i,1,n) e[i].clear();For(i,1,n) scanf("%d",&id[i]),e[id[i]].p_b(i);int u,v,w;For(i,1,m){scanf("%d %d %d",&u,&v,&w);G[u].p_b(Edge(v,w));G[v].p_b(Edge(u,w));}for(int i=n+1,j=1;j<n;i++,j++){if(e[i-n].size()>0&&e[i-n+1].size()>0){for(int tt:e[i-n]){G[tt].p_b(Edge(i,c));G[i+n-1].p_b(Edge(tt,0));}for(int tt:e[i-n+1]){G[tt].p_b(Edge(i+n-1,c));G[i].p_b(Edge(tt,0));}}}dij();cout<<"Case #"<<cas<<": ";if(n<1||dis[n]==INF) cout<<-1<<"\n";else cout<<dis[n]<<"\n";}return 0;
}