alan23273850 的刷題筆記
d282: 11015 - 05-2 Rendezvous
Tags: floyd-warshall, graph
出處：https://zerojudge.tw/ShowProblem?problemid=d282
提交：https://zerojudge.tw/Submissions?problemid=d282&account=allllllan123456
問題：給定 $N\in[1,22]$ 個點、$M\in[1,N(N-1)/2]$ 條記錄走過該路段所需花費 $[1,1000]$ 的無向邊，想請問選定哪個點為中央伍，可以使得其他點到此中央伍的花費總和最小？
解法：這題頂點數少，欲求的頂點對數量多，自然會想要用 Floyd-Warshall algorithm，而且還是典型的成本求和，難度自然不高。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int N, M, ans, miN, cases=0, cost[23][23]; string m[23];
6 while (cin >> N >> M && N) { miN = INT_MAX;
7 memset(cost, 0x7f, sizeof cost); // 一個 byte 的最大值
8 for (int i=1; i<=N; i++) cin >> m[i], cost[i][i] = 0;
9 for (int b, c, d; M--;) cin >> b >> c >> d, cost[b][c] = cost[c][b] = d;
10 for (int k=1; k<=N; k++)
11 for (int i=1; i<=N; i++)
12 for (int j=i+1; j<=N; j++)
13 cost[j][i] = cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
14 for (int i=1; i<=N; i++) {
15 int sum = accumulate(cost[i]+1, cost[i]+N+1, 0);
16 if (sum < miN) miN = sum, ans = i;
17 }
18 cout << "Case #" << (++cases) << " : " << m[ans] << '\n';
19 }
20 return 0;
21}