題目: UVa - 11463 - Commandos
題目說明
給一個無向圖,每條邊的 cost 皆為 1,給一個起點及終點,求從起點到某一點後再到終點所需要的最大 cost。
Input: 第一個整數 T
,表示有 T
組測資,每組測資前兩個數字為 n
、m
,依序表示圖上有 n
個點 ( 0 ~ n
- 1 ),及 m
條邊,後面 m
行,每行有兩個整數 u
、v
,表示 u
、 v
兩點是連通的。
Output: 輸出從起點到某一點後再到終點所需要的最大 cost。
解題思路
All Pair Shortest Path 題,讀測資並做 Floyd-Warshall Algorithm 求解即可。
參考解法
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
| #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 C; int n, m; int dist[101][101];
void init() { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) dist[i][j] = INF; dist[i][i] = 0; } }
void read() { cin >> n >> m; init();
int u, v; while (m--) cin >> u >> v, dist[u][v] = dist[v][u] = 1; }
void FloydWarshall() { for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]); } }
void solve() { int b, e, mx = INT_MIN; cin >> b >> e;
for (int k = 0; k < n; ++k) mx = max(dist[b][k] + dist[k][e], mx); cout << "Case " << ++C << ": " << mx << '\n'; }
int main() { int T; cin >> T; while (T--) { read(); FloydWarshall(); solve(); } }
|
參考資料
UVa 11463 - Commandos_小白菜又菜-CSDN博客