P – The Shortest Path in Nya Graph（建图/最短路）

InputThe 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 <= 10 ⁵) and C(1 <= C <= 10 ³), which is the number of nodes, the number of extra edges and cost of moving between adjacent layers.
The second line has N numbers l _i (1 <= l _i <= N), which is the layer of i ^th node belong to.
Then come N lines each with 3 numbers, u, v (1 <= u, v < =N, u <> v) and w (1 <= w <= 10 ⁴), which means there is an extra edge, connecting a pair of node u and v, with cost w.OutputFor 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个点，n层楼，相邻楼层之间可以相通，权值为c。还有m条双向边联通点。
题解：问题在于建图，m条边直接连接，然后将楼层看作另外的n个点，将楼层连向楼层上的点，权值为0，将点连向相邻楼层，权值为c。
这里本来要相邻的都有才能连接，但因为是单向边，直接将有点的楼层的点与相邻的连接即可。
要注意连接边的方向要从i->n+v->n+v-1/n+v+1->下一个点，反过来是不行的，可以验证一下。另外如果将点与对应楼层连成双向边，就多余了。

代码：

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(init,b,c) make_pair(init,make_pair(b,c))
#define rep(i,init,n) for (int i=init;i<=n;i++)
#define per(i,init,n) for (int i=n;i>=init;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll init, ll b) { return b ? gcd(b, init%b) : init; }
const int INF = 0x3f3f3f3f;
const int MAXN=200010;
struct qnode      //优先队列的创建（储存节点v以及到源点的距离C）
{
    int v;//节点v
    int c;//源点的距离（用来排序）
    qnode(int _v=0, int _c=0):v(_v),c(_c){}  //初始化为0？？？
    bool operator<(const qnode &r)const//定义优先队列的排序方式（实际上可以用pair进行替代），先比较第一维，相等时比较第二维 
    { return c>r.c;}
};
 
struct Edge//边结构
{
    int v,cost;    //储存边以及权  
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}//初始化？？？
};
vector<Edge>E[MAXN];//看作二维数组，每个i数组储存着从i边到下一边的所有数据
bool vis[MAXN];//标记数组
int dist[MAXN];//离源点的距离
void Dijkstra(int n, int start)     //点的编号从1开始，n是点的个数，start是源点
{
    memset(vis, false, sizeof(vis));//初始化标记数组
    for(int i = 1; i <= n;i++)dist[i] = INF;//初始化距离数组
    priority_queue<qnode>que;//创建定义的优先队列，类型为qnote
    while(!que.empty()) que.pop();//清空队列（这里不明白为什么要清空，是赋了初值吗？那为什么要赋初值）
    dist[start]=0;//源点到源点的距离初始化为0，以便于得出后续
    que.push(qnode(start,0));//源点入队，距离为0
    qnode tmp;//qnode类型的中转变量
    while(!que.empty()){//只要队列不为空，也可以看作每次出队都是一轮松弛
        tmp=que.top();//将队列中d最小的赋给tmp
        que.pop();//出队
        int u = tmp.v;//方便后续的操作，令u=该点的序号
        if(vis[u])continue;//如果已被标记，那么跳过
        vis[u]=true;//标记
        for(int i=0;i<E[u].size();i++){//循环u的下一点的个数次 
            int v=E[tmp.v][i].v;//v=（点u数组中的下一点） 
            int cost=E[u][i].cost; //cost = （点u数组中到下一点的距离） 
            if(!vis[v]&&dist[v]>dist[u]+cost){ //松弛操作
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));//入队
            }
        }
    }
}
 
void addedge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}

bool lay[MAXN];
int main(){
	int t;
	int cal=0;
	scanf("%d", &t);
	while(t--){
		
		int n,m,c;
		scanf("%d%d%d", &n,&m,&c);
		for(int i=1; i<=n*2; i++)E[i].clear();
//		memset(lay,false,sizeof(lay));
		int v,u;
		rep(i,1,n){
			scanf("%d",&v);
//			lay[v] = true;
			if(v>1)addedge(i,v-1+n,c);
            if(v<n)addedge(i,v+1+n,c);
//			addedge(i,v+n,0);	
			addedge(v+n,i,0);
		}
//		rep(i,1,n-1){
//			if(lay[i]&&lay[i+1]){
//				addedge(n+i,n+i+1,c);
//				addedge(n+i+1,n+i,c);
//			}
//		}
		rep(i,1,m){
			scanf("%d%d%d",&u,&v,&c);
			addedge(u,v,c);
			addedge(v,u,c);
		}
		Dijkstra(2*n,1);
		printf("Case #%d: %d\n", ++cal,dist[n]==INF?-1:dist[n]);
	}
	
	return 0;
}