商店选址问题[亲测有效]

大家好，欢迎来到IT知识分享网。

#题目大意：
Description

给出一个城市的地图（用邻接矩阵表示），商店设在一点，使各个地方到商店距离之和最短。

Input

第一行为n（共有几个城市）； N小于201
第二行至第n+1行为城市地图（用邻接矩阵表示）；

Output

最短路径之和；

Sample Input

3
0 3 1
3 0 2
1 2 0

Sample Output

3

#解题思路：
数据较小，用Floyd算法O（n^3）就够了

#源程序：

#include <cstdio>
#define r(i,a,b) for(int i=a;i<=b;i++)
#define inf 1000000001
using namespace std;
int f[201][201],a[201],n,x,y;
void read(int &f) //read和write看不懂就算了，只要知道是输入输出就好了
{  
    f=0;char c;bool d=0;  
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=1;f=f*10+c-48;  
    while (c=getchar(),c>='0'&&c<='9') f=f*10+c-48;  
    if (d) f*=-1;  
}  
void write(int x)  
{  
    if (!x) {
				putchar(48);
				return;
			}  
    if (!(x/10)){
					putchar(x%10+48);
					return;
				}  
    write(x/10);
	putchar(x%10+48);  
}
int min(int x,int y)
{
	return x>y?y:x;
}
int main()
{
	int minn=99999999;
	read(n);
	r(i,1,n)
	 r(j,1,n)
	 {
	 	read(f[i][j]);
	 	if(f[i][j]==0&&i!=j) f[i][j]=99999999;//我提交的题库数据有bug
	 } 
	r(k,1,n)//最短路径，Floyd
	 r(i,1,n)
	  r(j,1,n)
	   if (f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];
	r(i,1,n)//求最短路径之和
    {  
        int ans=0;  
        r(j,1,n)
		 ans+=f[i][j];
        if (ans<minn)
            minn=ans;
    }  
	write(minn);
	return 0;
}