趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 jd3 於 2015-3-19 13:22 編輯
http://uva.onlinejudge.org/index ... roblem&problem=1956
題意:
大致上是說要找到一個點讓所有人點到那裏的總距離最短
想法:
嗯......一臉最短路
只是要算的是各點到那裏的最短距離總和
再從中找最小的
沒想到什麼特別的解法,就用最短路的演算法寫吧
解法:
法1:
直觀的枚舉每個點
對每個點做一次 Dijkstra 算總和
時間複雜度 O(V*E*log(E) )
法2:
其實只要做一次 Floyd-Warshall 得到全點對最短距離 → O(V^3)
再用 O(V^2) 枚舉所有點當目的地的情況就OK了
總複雜度 = O(V^3)
比較:
因為 E 最多是 V^2 級別
所以法1可以換算成 O(V^3 * log(V^2))
所以從複雜度來看法2比較快
能簡則簡
F-W好寫很多
全點對能用F-W 就不要用 Dijkstra
有時候複雜度會爛掉owo
[C++] 純文本查看 復制代碼 #include<iostream>
#include<cstdio>
#define INF 1000000000
using namespace std;
int n,m;
int dist[30][30];
string name[100];
void FW()
{
for(int j = 1 ; j <= n ; j++)
for(int i = 1 ; i <= n ; i++)
for(int k = 1 ; k <= n ; k++)
dist[i][k] = min(dist[i][k], dist[i][j]+dist[j][k]);
}
int main()
{
for(int time = 1 ; ; time++)
{
cin >> n >> m;
if(n==0 && m==0)
return 0;
int a,b,w;
for(int i = 1 ; i <= n ; i++)
cin >> name[i];
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
dist[i][j] = INF;
for(int i = 1 ; i <= n ; i++)
dist[i][i] = 0;
for(int i = 1 ; i <= m ; i++)
{
cin >> a >> b >> w;
if(w < dist[a][b])
{
dist[a][b] = w;
dist[b][a] = w;
}
}
FW();
int ans, min_sum = INF;
for(int i = 1 ; i <= n ; i++)
{
int sum = 0;
for(int j = 1 ; j <= n ; j++)
{
sum += dist[i][j];
// printf("%d %d = %d\n",i,j,dist[i][j]);
}
// cout << "sum = " << sum << endl;
if(sum < min_sum)
{
min_sum = sum;
ans = i;
}
}
cout << "Case #" << time << " : " << name[ans] << endl;
}
return 0;
}
|