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

# 題目說明

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

---

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

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

最後有兩個數字a和b

---

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

# 解題方法

先將g1(無向圖)、g2(有像圖)建圖
將值設為101是因為N最多100，101對於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