（ssl 1760）商店选址问题#floyd，dijkstra#

题目

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

---

分析

最短路径，floyd或dijsktra

---

代码

#include <cstdio>
using namespace std;
int n,f[201][201],s,min=2147483647;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++) {
	scanf("%d",&f[i][j]);
	if (!f[i][j]) f[i][j]=2147483647;
	}
	for (int k=1;k<=n;k++)
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	if (f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j];
	
	for (int i=1;i<=n;i++){
	s=0; for (int j=1;j<=n;j++) s+=f[i][j]; if (min>s) min=s;
	}
	printf("%d",min); return 0;
}

floyd

#include <cstdio>
#include <cstring>
using namespace std;
int n,low[202],f[202][202],ans=2147483647; bool b[202]; 
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++) {
	scanf("%d",&f[i][j]);
	if (!f[i][j]) f[i][j]=2147483647;
	}
	for (int l=1;l<=n;l++){
	memset(b,0,sizeof(b)); b[l]=1; int s=0;
	for (int i=1;i<=n;i++) low[i]=f[l][i];
	for (int i=1;i<n;i++){
		int minx=2147483647,k=0;
		for (int j=1;j<=n;j++)
		if (!b[j]&&low[j]<minx){minx=low[j];k=j;}
		if (k==0) break; b[k]=1;
		for (int j=1;j<=n;j++) if ((long long)low[k]+f[k][j]<low[j]) low[j]=low[k]+f[k][j];//更新最小值
	} 
	for (int i=1;i<=n;i++) if (low[i]!=2147483647)s+=low[i];//最短路径和
	if (ans>s) ans=s;
	}
	printf("%d",ans);
}