# 題目: 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