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

本文主要是介绍（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);
}

这篇关于（ssl 1760）商店选址问题#floyd，dijkstra#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---