SSL

xiaoxiao2021-02-28  15

题意:

    求一个图中在哪里放商店使商店到每个点的最短距离的和最短。

思路:

    先用floyd算法求出每两个点之间的最短距离最后再统计最小值就好了。

代码:

#include<cstdio> #include<algorithm> using namespace std; int n,f[201][201],max1,min1; 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]==0&&i!=j) f[i][j]=2100000000;//如果两点为零代表没连通就让它变成一个很大的值 } for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (f[i][k]+f[k][j]<f[i][j]) f[i][j]=f[i][k]+f[k][j];//用floyd求出最短距离 min1=2100000000; for (int i=1;i<=n;i++) { max1=0; for (int j=1;j<=n;j++) max1=max1+f[i][j];//求出每个点到其它点最短距离的和 min1=min(max1,min1);//找出最小的 } printf("%d",min1); }
转载请注明原文地址: https://www.6miu.com/read-1600258.html

最新回复(0)