d282 - 11015 - 05-2 Rendezvous
題目描述
題目要求找出一個地點，使得所有組員到該地點的總路程消耗最小。給定組員數量 N，路徑數量 M，以及各路徑的起點、終點和消耗值，需要計算從每個組員家出發到其他組員家的最短路徑，然後計算從每個組員家作為集合地點時，所有組員的路程總消耗，並找到消耗最小的組員。
解題思路
本題可以使用 Floyd-Warshall 演算法計算所有組員之間的最短路徑。Floyd-Warshall 演算法可以有效地計算圖中所有頂點對之間的最短路徑。計算完最短路徑後，對於每個組員，計算所有其他組員到該組員的最短路徑之和。選擇路徑總和最小的組員作為集合地點。如果有多個組員的路徑總和相同，則選擇第一個出現的組員。
複雜度分析
- 時間複雜度: O(N^3)，其中 N 是組員數量。Floyd-Warshall 演算法的時間複雜度為 O(N^3)，計算每個組員的路徑總和需要 O(N) 的時間，因此總時間複雜度為 O(N^3)。
- 空間複雜度: O(N^2)，其中 N 是組員數量。Floyd-Warshall 演算法需要一個 N x N 的矩陣來存儲最短路徑，因此空間複雜度為 O(N^2)。
程式碼
#include <iostream>
using namespace std;
int an[25][25],n,m,x,y,k,ca;
string name[25];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
for(int i=0;i<n;++i)
cin >> name[i];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
(i==j)?an[i][j]=0:an[i][j]=500000;
while(m--){
cin >> x >> y >> k;
--x;--y;
an[x][y]=an[y][x]=k;
//an[x][y]=min(an[x][y],k);an[y][x]=min(an[y][x],k);
}
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)
an[j][k]=min(an[j][k],an[j][i]+an[i][k]);
int ans=5000000;
for(int i=0;i<n;++i){
int tmp=0;
for(int j=0;j<n;++j)
tmp+=an[i][j];
ans=min(tmp,ans);
//cout << tmp << " " << name[i] << "\n";
}
for(int i=0;i<n;++i){
int tmp=0;
for(int j=0;j<n;++j)
tmp+=an[i][j];
if(tmp==ans){
cout << "Case #" << ++ca << " : " << name[i] << "\n";
break;
}
}
}
}