商店選址問題

ssl 1760

題目大意：

有一些點，在一個點上按醫院，有一個值就是這個點到其他點的最短路之和，問這個值最小是多少

原題：

Description

給出一個城市的地圖（用鄰接矩陣表示），商店設在一點，使各個地方到商店距離之和最短。

Input

第一行為n（共有幾個城市）； N小于201
第二行至第n+1行為城市地圖（用鄰接矩陣表示）；

Output

最短路徑之和；

Sample Input

3 0 3 1 3 0 2 1 2 0

Sample Output

3

解題思路：

直接用鄰接矩陣存，然后Floyed，再統計一下取最小就可以了

代碼：

#include<cstdio> using namespace std; int n,sum,ans,f[205][205]; 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 (i!=j&&f[i][j]==0) f[i][j]=2147483647;//一個BUG}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])//Floyedf[i][j]=f[i][k]+f[k][j];ans=2147483647;//預處理for (int i=1;i<=n;++i){sum=0;//清零for (int j=1;j<=n;++j)sum+=f[i][j];//統計if (sum<ans) ans=sum;//取最小}printf("%d",ans); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【Floyed】【最短路】商店选址问题（ssl 1760）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。