南京电器网站建设,赣州吧百度贴吧,wordpress做中文官网,厦门手机建站商店选址问题
ssl 1760
题目大意#xff1a;
有一些点#xff0c;在一个点上按医院#xff0c;有一个值就是这个点到其他点的最短路之和#xff0c;问这个值最小是多少
原题#xff1a;
Description
给出一个城市的地图#xff08;用邻接矩阵表示#xff09;…商店选址问题
ssl 1760
题目大意
有一些点在一个点上按医院有一个值就是这个点到其他点的最短路之和问这个值最小是多少
原题
Description
给出一个城市的地图用邻接矩阵表示商店设在一点使各个地方到商店距离之和最短。
Input
第一行为n共有几个城市 N小于201 第二行至第n1行为城市地图用邻接矩阵表示
Output
最短路径之和
Sample Input
3
0 3 1
3 0 2
1 2 0Sample Output
3解题思路
直接用邻接矩阵存然后Floyed再统计一下取最小就可以了
代码
#includecstdio
using namespace std;
int n,sum,ans,f[205][205];
int main()
{scanf(%d,n);for (int i1;in;i)for (int j1;jn;j){scanf(%d,f[i][j]);if (i!jf[i][j]0) f[i][j]2147483647;//一个BUG}for (int k1;kn;k)for (int i1;in;i)for (int j1;jn;j)if (f[i][k]f[k][j]f[i][j])//Floyedf[i][j]f[i][k]f[k][j];ans2147483647;//预处理for (int i1;in;i){sum0;//清零for (int j1;jn;j)sumf[i][j];//统计if (sumans) anssum;//取最小}printf(%d,ans);
}
