# 題目: UVa 10171 - Meeting Prof. Miguel

# 題目說明

給一個有weight的有向圖，圖中的道路有年齡限制
給Y與M的起始點，求Y與M要會合的最短路徑

---

INPUT:
每筆測資第一行輸入一個整數N，代表接下來有N行

接著輸入四個大寫字元age、connect、u、v，與一個整數w

1. age = Y代表只有年輕人能走的路、age = M代表只有老人能走的路
2. connect = U為單向連通、connect = B為雙向連通
3. u連接到v的weight(cost)為w

接下來有兩個大寫字元y與m，前者代表年輕人的起始點，後者代表老人的起始點

當N為0時結束程式

---

OUTPUT:
輸出Y與M會合的最短路徑與會合的點
如果無法會合，則輸出You will never meet.

# 解題方法

定義兩個vector< vector<int> >，分別為G[0]與G[1]
G[x][i][j]代表從i到j的最短路徑
先將G[x]中所有元素設為501，相當於無限大 (題目限制範圍為< 500)

判斷age為年輕人(tmp = 0)或老人(tmp = 1)
將G[tmp][U][V]設為w，若為雙向則將G[tmp][V][U]設為w

接下來跑Floyd-Warshall algorithm (佛洛依德演算法)
轉移方程為: G[tmp][i][j] = min(G[tmp][i][j], G[tmp][i][k] + G[tmp][k][j])

最後判斷是否會合，與輸出匯合點

# 參考程式碼

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() 
{
	// fast io
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int N, w, U, V, Y, M, tmp;
	char age, connect, u, v, y, m;
	vector< vector<int> > G[2];

	while (cin >> N, N)
	{
		// init
		G[0].assign(26, vector<int>());
		G[1].assign(26, vector<int>());
		for (int i = 0; i < 26; ++i) G[0][i].assign(26, 501), G[1][i].assign(26, 501);
		int Max = 0;
		int ans = 501;

		// store data in target graph
		for (int i = 0; i < N; ++i)
		{
			cin >> age >> connect >> u >> v >> w;
			U = u - 'A';
			V = v - 'A';

			if (age == 'Y') tmp = 0;
			else tmp = 1;

			G[tmp][U][V] = w;
			if (connect == 'B') G[tmp][V][U] = w;
			
			Max = max(Max, max(U, V));
		}
		for (int i = 0; i < 26; ++i) G[0][i][i] = G[1][i][i] = 0;

		// Floyd-Warshall algorithm
		for (int k = 0; k <= Max; ++k) for (int i = 0; i <= Max; ++i) for (int j = 0; j <= Max; ++j)
		{
			G[0][i][j] = min(G[0][i][j], G[0][i][k] + G[0][k][j]);
			G[1][i][j] = min(G[1][i][j], G[1][i][k] + G[1][k][j]);
		}

		cin >> y >> m;
		Y = y - 'A';
		M = m - 'A';

		for (int i = 0; i <= Max; ++i) ans = min(ans, G[0][Y][i] + G[1][M][i]);
		
		if (ans == 501) cout << "You will never meet.\n";
		else
		{
			cout << ans;
			for (int i = 0; i <= Max; ++i) if (ans == G[0][Y][i] + G[1][M][i]) cout << " " << char(i + 'A');
			cout << "\n";
		}
	}

	return 0;
}

# 參考資料

https://github.com/morris821028/UVa/blob/master/volume101/10171%20-%20Meeting%20Prof.%20Miguel.cpp