題目連結: https://zerojudge.tw/ShowProblem?problemid=d282
# 內容
我們的小組想在一個地方集合並且作功課。我們這個 05-2 小組有 22 個組員。因為我們有點疑惑哪裡是跟大家見面的最好地方。所以我們決定在一個可以讓總耗費的量最少的地方見面。總耗費量的定義是從所有人到目的地的總距離。在本題中，你被要求寫一個程式來找出有機會能夠有最少耗費量的地點，而每個組員的家就是那些可能的地點。
# 解題思路
先求所有兩點之間的最短距離，
再加總求每個人到其他人的路徑總合最小
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int n,m,dist[23][23],times = 0; | |
string name[23]; | |
int main(){ | |
while(cin>>n>>m&&n&&++times){ | |
memset(dist,0x3f3f3f3f,sizeof(dist)); | |
for(int i = 1;i<=n;i++)dist[i][i]=0; | |
for(int i = 1;i<=n;i++) | |
cin>>name[i]; | |
for(int i = 0,a,b,k;i< m;i++) { | |
cin>>a>>b>>k; | |
if(dist[a][b]>k) | |
dist[a][b] = dist[b][a] = k; | |
} | |
for(int i = 1;i<=n;i++)for(int j = 1;j<=n;j++)for(int k = 1;k <=n;k++) | |
if(dist[i][j]>dist[j][k]+dist[k][i]) | |
dist[i][j] = dist[j][i] = dist[j][k]+dist[k][i]; | |
int ans = 0x3f3f3f,now_i; | |
for(int i = 1,sum = 0;i<=n;i++,sum=0){ | |
for(int j = 1 ; j<=n;j++) | |
sum += dist[i][j]; | |
if(ans>sum) | |
ans = sum,now_i = i; | |
} | |
cout<<"Case #"<<times<<" : "<<name[now_i]<<'\n'; | |
} | |
return 0; | |
} |
