11015 - 05-2 Rendezvous

jd3

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;
}