UVa 11833 Route Change

題意：
    第一行有N M C K四個數字，N表示有N個地點(編號0~N-1)，M表示有M條路線，C-1為終點編號，K為出發點編號。
    底下有M行，每行u v d三個數字，分別表示u到v和v到u這條路線需要花費d元。
    本題特別的要求為，0~C-1為特殊地點，只要踏入0~C-1這C個地點內，例如i這個點<=C-1，之後的路徑就只能依照i, i+1, i+2, .....,C-1這樣走，只要不在特殊地點，就能前往任意其他地方，本題求K到C-1的最小花費。

想法：
    依題目輸入將M條路線建好dis[u][v]=d，其他沒有連通的路線為INF。輸入完成後我們將編號小於C-1的點i，算出dis[i][C-1]，等等SPFA用到。
    然後做K到C-1的SPFA最短路徑，注意如果踏入的點(nxt)為特殊地點(nxt<C)，不要丟入queue裡面，而是直接判斷cost[C-1]=min(cost[C-1], cost[nxt]+dis[nxt][C-1])，其他不是特殊地點的nxt，則依照一般SPFA把nxt丟入queue即可。

	#include <cstdio>
	#include <queue>
	#include <cstring>
	using namespace std;
	#define INF 999999999
	int dis[260][260];
	int cost[260];
	int main()
	{
	int N, M, C, K;
	while (scanf("%d %d %d %d", &N, &M, &C, &K) && (N || M || C || K)) {
	// Initial
	for (int i = 0; i < N; ++i) {
	cost[i] = INF;
	fill(dis[i], dis[i]+N, INF);
	dis[i][i] = 0;
	}
	// Input
	int u, v, d;
	for (int i = 0; i < M; ++i) {
	scanf("%d %d %d", &u, &v, &d);
	dis[u][v] = dis[v][u] = d;
	}
	// 編號小於C-1的點到C-1的距離
	for (int i = C-2; i >= 0; --i)
	dis[i][C-1] = dis[i][i+1] + dis[i+1][C-1];
	// SPFA
	queue<int> Q;
	bool inQueue[260] = {0};
	Q.push(K);
	cost[K] = 0;
	inQueue[K] = true;
	while (!Q.empty()) {
	int cur = Q.front();
	inQueue[cur] = false;
	Q.pop();
	for (int nxt = 0; nxt < N; ++nxt) {
	if (cost[nxt] > cost[cur] + dis[cur][nxt]) {
	cost[nxt] = cost[cur] + dis[cur][nxt];
	if (nxt < C) { // nxt 為特殊地點
	cost[C-1] = min(cost[C-1], cost[nxt] + dis[nxt][C-1]);
	}
	else if (!inQueue[nxt]) {
	Q.push(nxt);
	inQueue[nxt] = true;
	}
	}
	}
	}
	printf("%d\n", cost[C-1]);
	}
	}

view raw [UVa] 11833 Route Change.cpp hosted with ❤ by GitHub