HDU 4725 The Shortest Path in Nya Graph（最短路）

题意：有N个点和N层..一层有X个点(1<=X<=N).两邻两层间有一条路花费C。还有M条小路在两个点之间。问从第一个点走到第N个点最短路是多少。

思路：这道题多了一个层的东西，如果把任意两层间的点连一条边那么边的数量可能达到O（n*n），所以换一种处理方法，用堆优化的Dijkatra算法，

因为如果之前用过层x的点更新源点到x+1的点之间的距离，那么之后更新源点到x+1的点的最短距离就不用考虑层x到x+1这条边了，这是因为Dijkatra算法优先考虑的是层x中距离最小的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int MAXN = 100100;
const int INF = 0x3f3f3f3f;
struct Edge {
	int from, to, w;
	int next;
} edge[MAXN*10];
int n, m, c, tot, head[MAXN];
int node[MAXN];
vector<int> layer[MAXN];
void addedge(int u, int v, int c) {
	edge[tot].from = u;
	edge[tot].to = v;
	edge[tot].w = c;
	edge[tot].next = head[u];
	head[u] = tot++;
}
int vis[MAXN];
struct HeapNode {         ///用到的优先队列的结点
	int d, u;
	bool operator < (const HeapNode& rhs) const {
		return d > rhs.d;
	}
};
struct Dijkstra {
	bool done[MAXN];            //是否已经永久编号
	int d[MAXN];                //s到各个点的距离

	void dijkstra(int s) {            //求s到所有点的距离
		priority_queue<HeapNode> Q;
		for(int i = 1; i <= n; i++) d[i] = INF;
		d[s] = 0;
		memset(done, 0, sizeof(done));
		Q.push((HeapNode){0, s});
		while(!Q.empty()) {
			HeapNode x = Q.top(); 
			Q.pop();
			int u = x.u;
			if(done[u]) continue;
			done[u] = true;
			for(int i = head[u]; i != -1; i = edge[i].next) {
				Edge& e = edge[i];
				if(d[e.to] > d[u] + e.w) {
					d[e.to] = d[u] + e.w;
					Q.push((HeapNode){d[e.to], e.to});
				}
			}
			if(!vis[node[u]]) {
				vis[node[u]] = 1;
				if(node[u] != 1) {
					for(int i = 0; i < layer[node[u]-1].size(); i++) {
						if(d[layer[node[u]-1][i]] > x.d+c) {
							d[layer[node[u]-1][i]] = x.d+c;
							Q.push((HeapNode){x.d+c, layer[node[u]-1][i]});
						}
					}
				}
				if(node[u] != n) {
					for(int i = 0; i < layer[node[u]+1].size(); i++) {
						if(d[layer[node[u]+1][i]] > x.d+c) {
							d[layer[node[u]+1][i]] = x.d+c;
							Q.push((HeapNode){x.d+c, layer[node[u]+1][i]});
						}
					}
				}
			}
		}
	}
} dij;
void init() {
	tot = 0;
	memset(head, -1, sizeof(head)); 
	memset(vis, 0, sizeof(vis));
	for(int i = 1; i <= n; i++) layer[i].clear();	
}
int main() {
    //freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    int kase = 0;
	while(T--) {
		cin >> n >> m >> c;
		init();
		for(int i = 1; i <= n; i++) {
			scanf("%d", &node[i]);
			layer[node[i]].push_back(i);
		}
		for(int i = 1; i <= m; i++) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			addedge(u, v, w);
			addedge(v, u, w);
		}
		printf("Case #%d: ", ++kase);
		dij.dijkstra(1);
		if(dij.d[n] == INF) puts("-1");
		else printf("%d\n", dij.d[n]);
	}
    return 0;
}