The Shortest Path in Nya Graph

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16403 Accepted Submission(s): 3423

Problem Description
This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this paragraph, just move on.
The Nya graph is an undirected graph with “layers”. Each node in the graph belongs to a layer, there are N nodes in total.
You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.

Input
The first line has a number T (T <= 20) , indicating the number of test cases.
For each test case, first line has three numbers N, M (0 <= N, M <= 105) and C(1 <= C <= 103), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers li (1 <= li <= N), which is the layer of ith node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 104), which means there is an extra edge, connecting a pair of node u and v, with cost w.

Output
For test case X, output "Case #X: " first, then output the minimum cost moving from node 1 to node N.
If there are no solutions, output -1.

Sample Input
2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3

3 3 3
1 3 2
1 2 2
2 3 2
1 3 4

Sample Output
Case #1: 2
Case #2: 3

题目大意：有n个顶点m条边每条边有各自权值，求顶点1到n的最短距离，其实题目就是这个意思，不过在这之上加了一个难点，那就是每个顶点有对应的层次，x层到x+1层有一个其他的权值（题目给的），然后在这条件下找最短路。
思路：这题难点就是建图，建完图后跑一个优化的dijkstra就好了，建图我是看的别的大佬写的，不过他写错了，交上去wa，然后我根据他的错误更正了并且ac了。题目中给出n个点，我们可以抽象出n2个点，（和并查集的食物链类似），然后用n个点和n+1到n+2i建立关系，然后达到1到n有了层次关系这样一个效果。（难点就是虚拟的这另外n个点，需要自己画图模拟一下，多花一点时间就可以看懂了），然后考虑层次为1，只能建立对应边和下一层边，考虑层次x（x>1&&x<n），建立对应边还有上一层和下一层的边，考虑层次=n，只能建立对应边和上一层的边。以上建立边都是在另外n个点的基础上建立的，下面给出代码。

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long int ll;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;

typedef struct{
	ll to,w,nxt;
}edge;
struct node{
	ll id,dis;
	node(ll a,ll b):id(a),dis(b){}
	bool operator <(const node &a)const{
		return dis>a.dis;
	}
};
ll t,n,m,c,u,v,w;
ll cnt=0;
edge e[maxn*8];
ll head[maxn*2],dis[2*maxn],va[2*maxn];

void add(ll from,ll to,ll w){
	e[++cnt].to=to;
	e[cnt].w=w;
	e[cnt].nxt=head[from];
	head[from]=cnt;
}

void dijkstra(ll s){
	for(ll i=1;i<=n*2;i++)dis[i]=inf;
	dis[s]=0;
	priority_queue<node>st;
	st.push(node(s,0));
	while(!st.empty()){
		node f=st.top();st.pop();
		ll u=f.id;ll d=f.dis;
		if(d!=dis[u])continue;
		for(ll i=head[u];i;i=e[i].nxt){
			ll v=e[i].to;ll w=e[i].w;
			if(dis[v]>w+dis[u]){
				dis[v]=w+dis[u];
				st.push(node(v,dis[v]));
			}
		}
	}
	if(dis[n]>=inf||n==0){
		printf("-1\n");
	}else{
		printf("%lld\n",dis[n]);
	}
}
void nin(){
	cnt=0;
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	memset(va,0,sizeof(va));
}
int main(){
	scanf("%lld",&t);
	ll x,y,z;
	for(int h=1;h<=t;h++){
		nin();
		scanf("%lld%lld%lld",&n,&m,&c);
		for(int i=1;i<=n;i++){
			scanf("%lld",&x);
			add(i,x+n,0);
			if(x>1){
				add(i,n+x-1,c);
				add(n+x-1,i,c);
			}
			if(x<n){
				add(i,n+x+1,c);
				add(n+x+1,i,c);
			}
		}
		for(int i=1;i<=m;i++){
			scanf("%lld%lld%lld",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		printf("Case #%d: ",h);
		dijkstra(1);
	}
}