題目： UVa - 12319 - Edgetown’s Traffic Jams
題目說明
給一個無向圖及一個有向圖，兩圖上的點數量一樣，求任兩點的最短路徑在有向圖上是否大於在無向圖上的 A 倍加 B。
Input： 每組測資第一個整數 N 表示有 N 個點 **( 編號為 1 ~ N )**，後面 N 行依序為無向圖的連接情況，再後面 N 行依序為有向圖的連接情況，每行至少有一個整數 u，後面的數字表示有 u 到該數字的邊，且邊的路徑長為 1。
Output： 若任兩點的最短路徑在有向圖上大於在無向圖上的 A 倍加 B 輸出 “Yes”，否則輸出 “No”。
解題思路
這個解法需要有 Floyd-Warshall 演算法的概念。
先讀取測資，若任兩點沒有邊連接，則路徑長初始化為無限大( 1e9 )，之後使用 Floyd-Warshall 演算法找出圖上任兩點的最短路徑，再依照題目要求判斷即可。
參考解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <bits/stdc++.h>
using namespace std;
static auto __ = []
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
const int inf = (int)1e9;
int N;
int a, b;
int G1[101][101];
int G2[101][101];
void init()
{
fill(G1[0], G1[0] + 101 * 101, inf);
fill(G2[0], G2[0] + 101 * 101, inf);
}
void readGraph(int (*G)[101])
{
int tmp;
string str;
stringstream ss;
for (int i = 1; i <= N; ++i)
{
getline(cin, str);
ss.clear();
ss.str(str);
ss >> tmp;
while (ss >> tmp) G[i][tmp] = 1;
}
}
void FloydWarshall()
{
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]);
}
}
}
bool solve()
{
for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j)
if (i != j && G2[i][j] > G1[i][j] * a + b) return false;
return true;
}
int main()
{
while ((cin >> N).ignore() && N)
{
init();
readGraph(G1);
readGraph(G2);
cin >> a >> b;
FloydWarshall();
if (solve()) cout << "Yes\n";
else cout << "No\n";
}
}
|
參考資料
Uva 12319 Edgetown’s Traffic Jams @ louisfghbvc的部落格 :: 痞客邦 ::
[演算法] 最短路徑 (Floyd-Warshall 演算法) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天
All-Pairs Shortest Path：Floyd-Warshall Algorithm
