# 題目: UVa 12319 - Edgetown's Traffic Jams'

# 題目說明

給一張無向圖,一張有像圖
求有像圖中任兩點的距離不能大於無向圖中任兩點距離的 a 倍 + b


INPUT:
第一行輸入一個整數 N ,代表無向圖及有像圖的大小
重複以下步驟兩次,分別為無向圖及有像圖

接下來有 N 行,每行至少有 2 個數字
設第 1 個數字為 u 、其後任一數字為 v ,則 u 連通至 v

最後有兩個數字 ab


OUTPUT:
符合條件則輸出 Yes ,反之輸出 No

# 解題方法

先將 g1 (無向圖)、 g2 (有像圖) 建圖
將值設為 101 是因為 N 最多 100101 對於 N 即為無限大

讀取連通的點,將連通的點設為 1

之後跑 Floyd-Warshall 演算法,找出每個點間的最短路徑
最後判斷是否符合題目要求

# 參考程式碼

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, v, u, a, b;
	string str;
	vector<int> g1[101], g2[101];
	while (cin >> N, N)
	{
		// init
		cin.ignore();
		for (int i = 1; i <= N; ++i)
		{
			g1[i].assign(N + 1, 101);
			g2[i].assign(N + 1, 101);
		}
		// store graph
		for (int i = 1; i <= N * 2; ++i)
		{
			getline(cin, str);
			stringstream ss(str);
			ss >> u;
			while (ss >> v) i <= N ? g1[u][v] = 1 : g2[u][v] = 1;
		}
		
		// Floyd-Warshall algorithm
		for (int k = 1; k <= N; ++k)
		{
			for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j)
			{
				g1[i][j] = min(g1[i][j], g1[i][k] + g1[k][j]);
				g2[i][j] = min(g2[i][j], g2[i][k] + g2[k][j]);
			}
		}
		cin >> a >> b;
		bool out = false;
		for (int i = 1; i <= N && !out; ++i) for (int j = 1; j <= N && !out; ++j)
		{
			if (i == j) continue;
			if (g2[i][j] > g1[i][j] * a + b) out = true;
		}
		cout << (out ? "No" : "Yes") << "\n";
	}
	return 0;
}

# 參考資料

https://ithelp.ithome.com.tw/articles/10209186
https://louisfghbvc.pixnet.net/blog/post/329756149-uva-12319-edgetown%E2%80%99s-traffic-jams