hdu 4725 The Shortest Path in Nya Graph(dijkstra+優先隊列)

題目鏈接：hdu 4725 The Shortest Path in Nya Graph

題目大意：n個點，m條邊，以及相鄰層之間移動的代價c，給出每個點所在的層數，以及m條邊，每條邊有u，v，val，表示從節點u到v（無向），並且移動的代價val，問說從1到n的代價最小是多少。

解題思路：dijkstra算法，主要是建圖，每一層有一個匯點，匯點連接所有處於當前層的點，代價為0，相鄰層之間如果兩層都有點的話，連接，代價為c，然後每個點連接上下層的匯點，代價c（這裡我一開始寫將當前點連接到當前層的匯點，結果WA了，還不知道原因）。剩下的就是dijkstra算了。

#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef pair pii;

const int N = 1e5;
const int INF = 0x3f3f3f3f;

int n, m, c, a[N*3+10], vis[N*3+10];
int nindex, g[N*3+10];

struct state {
	int v;
	int	val;
	int next;
}edge[N*20];

inline void addEdge (int u, int v, int val) {
	edge[nindex].v = v;
	edge[nindex].val = val;
	edge[nindex].next = g[u];
	g[u] = nindex++;
}

void init () {

	nindex = 0;
	memset(g, -1, sizeof(g));
	memset(vis, 0, sizeof(vis));
	scanf("%d%d%d", &n, &m, &c);

	int a, b, d;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d);
		vis[d] = 1;
	//	addEdge(i, d+N, 0);
		addEdge(d+N, i, 0);
		if (d > 1)
			addEdge(i, d + N - 1, c);
		if (d < n)
			addEdge(i, d + N + 1, c);
	}

	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &a, &b, &d);
		addEdge(a, b, d);
		addEdge(b, a, d);
	}

	for (int i = 2; i <= n; i++) {
		if (vis[i] && vis[i-1]) {
			addEdge(i+N, i-1+N, c);
			addEdge(i-1+N, i+N, c);
		}
	}
}

int dijkstra() {
	memset(a, INF, sizeof(a));

	priority_queue< pii, vector, greater > que; 

	a[1] = 0;
	que.push(make_pair(a[1], 1));

	while ( !que.empty()) {
		pii cur = que.top();
		que.pop();

		int x = cur.second;

		for (int j = g[x]; j != -1; j = edge[j].next) {
			int u = edge[j].v;

			if (a[u] > a[x] + edge[j].val) {
				a[u] = a[x] + edge[j].val;
				que.push(make_pair(a[u], u));
			}
		}
	}

	if (a[n] == INF)
		return -1;
	else
		return a[n];
}

int main () {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		init();
		printf("Case #%d: %d\n", i, dijkstra());
	}
	return 0;
}