UVa 10801 Lift Hopping

題意：
    有n個電梯(1<=n<=5)，每個電梯移動一層樓的時間不一樣，第i個電梯每層樓的移動時間以T[i]表示，而每個電梯能到達的樓層也不一樣，如果兩個電梯都能到達x樓，則能在x樓換另一台電梯搭乘，但轉換的時間為60秒。今天起點在第0樓，給定第k樓為要前往的樓層，問最短的時間?
想法：
    先以Weight[i][j]表示在'不轉換'電梯的情況下，i樓到j樓所需的最短時間，這個部份可以在輸入測資的過程中一起完成。然後再考慮轉換電梯的情況，以Dis[i]表示到達i樓的時間，用SPFA演算法，每次queue的時候就判斷 if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) 來不斷更新Dis[nxt]的值。

	#include <iostream>
	#include <sstream>
	#include <queue>
	using namespace std;
	#define Inf 99999999
	int main()
	{
	ios::sync_with_stdio(false);
	int n, k;
	int T[6];
	int Floor[100];
	int Weight[100][100];
	int Dis[100];
	while (cin >> n >> k)
	{
	for (int i = 1; i <= n; ++i)
	cin >> T[i];
	for (int i = 0; i < 100; ++i) {
	Dis[i] = Inf;
	for (int j = 0; j < 100; ++j)
	Weight[i][j] = Inf;
	}
	cin.ignore();
	for (int i = 1; i <= n; ++i) {
	string str;
	getline(cin, str);
	stringstream ss(str);
	int Count = 0;
	while (ss >> Floor[Count]) ++Count;
	for (int x = 0; x < Count; ++x)
	for (int y = x + 1; y < Count; ++y) {
	int f1 = Floor[x], f2 = Floor[y];
	if ((f2-f1)*T[i] < Weight[f1][f2])
	Weight[f1][f2] = Weight[f2][f1] = (f2-f1)*T[i];
	}
	}
	queue<int> Q;
	int inQueue[101] = {0};
	Dis[0] = 0;
	inQueue[0] = true;
	Q.push(0);
	while (!Q.empty()) {
	int now = Q.front();
	inQueue[now] = false;
	Q.pop();
	for (int nxt = 0; nxt < 100; ++nxt) {
	if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) {
	Dis[nxt] = Dis[now] + Weight[now][nxt] + 60;
	if (!inQueue[nxt]) {
	Q.push(nxt);
	inQueue[nxt] = true;
	}
	}
	}
	}
	if (k == 0) cout << 0 << endl; // 不加這行答案會是-60
	else if (Dis[k] == Inf) cout << "IMPOSSIBLE" << endl;
	else cout << Dis[k] - 60 << endl;
	// SPFA把起點也當成有轉換電梯了 所以答案要減掉60
	}
	}

view raw [UVa] 10801 Lift Hopping.cpp hosted with ❤ by GitHub