題目鏈接

題目大意

一個有n個點的圖中，求一個點，使得這個點到其他點的最短路的最長距離最短。

輸入數據中，有多組測試。每組測試第一行為n，接下來n行，每行第一個x，x_i表示第i個點和x個點有路徑。接下來x個數對a,b表示i到a的代價為b

最后輸出這個點和最長距離。

?

這道題是顯而易見的最短路了。但是我們發現這個題的起點不確定。所以不是單源最短路，不能用SPFA

這里介紹另外一種算法：floyd算法。

floyd算法主要解決的是多源最短路問題，范圍比SPFA更廣，但時間復雜度是O(n^3)。再看題目n≤100，符合條件。

floyd算法，簡而言之，就是找i,j兩個點，然后找一個中間點k，如果i->k+k->j的最短路徑比當前i->j更短，就更新i->j的最短路。

代碼如下:

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][j]=f[i][k]+f[k][j];}}}}　　

最后統計答案時，對于每一個點i，看看它到其他點的最短路的最大值。這樣，這道題的代碼就呼之欲出了。

參考代碼

#include<cstdio> #include<cstdlib> #include<cstring> int n; int f[105][105]; int main() {while(1){scanf("%d",&n);if(n==0)break;memset(f,63,sizeof(f));for(int i=1;i<=n;i++){f[i][i]=0;int x;scanf("%d",&x);for(int j=1;j<=x;j++){int soy1,soy2;scanf("%d %d",&soy1,&soy2);f[i][soy1]=soy2;}}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++){for(int j=1;j<=n;j++)printf("%d ",f[i][j]>10000?-1:f[i][j]);printf("\n");}*/int ans=2147483647,ans2=-1;for(int i=1;i<=n;i++){int tt=-1;for(int j=1;j<=n;j++){if(f[i][j]>999999){tt=-1;break;}if(f[i][j]>tt)tt=f[i][j];}if(tt!=-1 && tt<ans){ans=tt;ans2=i;}}if(ans2==-1)printf("disjoint\n");else printf("%d %d\n",ans2,ans);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/AFOer-lhy/p/7826007.html

總結

以上是生活随笔為你收集整理的【Step1】【floyd】poj1125-Stockbroker Grapevine的全部內容，希望文章能夠幫你解決所遇到的問題。

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