Convenient Location AOJ0189

本文主要是介绍Convenient Location AOJ0189，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意直接有道翻译

思路：Floyd算法计算出任意两点之间最短路径，遍历每一个点，计算路径和，取最小值

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <fstream>
const int MAX = 1e4+10;
const int INF = 1e6;using namespace std;int n;
int cs;
int d[MAX][MAX] = {0};//两点间最短距离 
int sum, ans;
int pos;//最合适位置 //弗洛伊德最短路径 
void  Floyd(){for(int i=0; i<=cs; i++)for(int j=0; j<=cs; j++)for(int k =0; k<=cs; k++){d[j][k] = min(d[j][k], d[j][i]+d[i][k]);}			
}//测试函数 
int main(){ifstream cin ("D:\\钢铁程序员\\程序数据\\062最佳宿舍.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}while(cin >> n, n){cs = 0;//最大城市编号 //i->i 距离为零，其他初始化为INF（因为数据不止一个） for(int i=0; i<=n; i++)for(int j=0; j<=n; j++){if(i == j)d[i][j] = 0;elsed[i][j] = INF;}for(int i=0; i<n; i++){int a, b, c;cin >> a >> b >> c;d[a][b] = c;d[b][a] = c;cs = max(cs, a);cs = max(cs, b);}Floyd();		//找最合适位置 ans = INF;for(int i=0; i<=cs; i++){sum = 0;for(int j=0; j<=cs; j++){sum += d[i][j];}if(sum < ans){pos = i;ans = sum;}} cout << pos << " " << ans << endl;}cin.close();//打开文件以后要关闭 return 0;
} 

 

这篇关于Convenient Location AOJ0189的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---