AOJ 0189 Convenient Location 题解 《挑战程序设计竞赛》

AOJ 0189 Convenient Location

上班族：A桑的实习办公室有多个，公司允许睡办公室，求找出一个办公室使得跑路最短。

2.5 它们其实都是“图”

最短路

基础的任意两点之间的距离Floyd-Warshall算法就行了。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAX_V 11
int d[MAX_V][MAX_V];	//	d[u][v]表示边e=(u,v)的权值，不存在的时候等于无穷大或者d[i][i] = 0
int V;					//	顶点数

int x[MAX_V];			// x[i]表示以i为起点时的最短路线之和

void warshall_floyd()
{
	for (int k = 0; k < V; ++k)
	{
		for (int i = 0; i < V; ++i)
		{
			for (int j = 0; j < V; ++j)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	int E;
	while (cin >> E, E)
	{
		memset(d, 0x3f, MAX_V * MAX_V * sizeof(int));
		for (int i = 0; i < MAX_V; ++i)
		{
			d[i][i] = 0;
		}
		V = 0;
		for (int i = 0; i < E; ++i)
		{
			int u, v, cost;
			cin >> u >> v >> cost;
			d[u][v] = cost;
			d[v][u] = cost;
			V = max(V, max(v, u) + 1);
		}
		warshall_floyd();
		memset(x, 0, V * sizeof(int));
		for (int i = 0; i < V; ++i)
		{
			for (int j = 0; j < V; ++j)
			{
				x[i] += d[i][j];
			}
		}
		int ans = min_element(x, x + V) - x;
		cout << ans << ' ' << x[ans] << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 0189 Convenient Location 题解 《挑战程序设计竞赛》