Course
可以參考我做的課程簡報：
MST & Shortest Path
Floyd-Warshall
多源最短路徑
求出任意兩點之間的最短路徑
Floyd-Warshall 是一種動態規劃 Dynamic Programming 問題
暴力的動態規劃
Floyd-Warshall 特色：三層 for 迴圈
生成步驟
- 遍歷所有點 i 到點 j 之間的距離和若 i 經過點 k 再到 j 是否會更短
- 若
dp[i][j] > dp[i][k] + dp[k][j] 則更新 dp[i][j]
Floyd-Warshall Example
Template
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
| #include<bits/stdc++.h>
using namespace std;
const int maxn = 200+5;
double distance(int x1, int y1, int x2, int y2){
return sqrt(((x1 - x2) * (x1 - x2)) + (y1 - y2) * (y1 - y2));
}
int N;
double dp[maxn][maxn];
void FloydWarshall(){
for(int k = 0; k < N; ++k){
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
double maxi = max(dp[i][k], dp[k][j]);
if(maxi < dp[i][j]) dp[i][j] = maxi;
}
}
}
}
int main(){
int Case = 1;
while(cin >> N && N){
int x[maxn], y[maxn];
for(int i = 0; i < N; ++i){
cin >> x[i] >> y[i];
}
memset(dp, 0.0, sizeof(dp));
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
dp[i][j] = distance(x[i], y[i], x[j], y[j]);
}
}
FloydWarshall();
cout << "Scenario #" << Case++ << "Frog Distance = " << fixed << setprecision(3) << dp[0][1] << endl;
}
}
|
UVA Problem
UVA10099 - The Tourist Guide
