北京商城网站建设报价,上虞区驿亭镇新农村建设网站,杭州标志设计公司,微信开发者工具是什么题目链接 题目大意 一个有n个点的图中#xff0c;求一个点#xff0c;使得这个点到其他点的最短路的最长距离最短。 输入数据中#xff0c;有多组测试。每组测试第一行为n#xff0c;接下来n行#xff0c;每行第一个x#xff0c;xi表示第i个点和x个点有路径。接下来x个数…题目链接 题目大意 一个有n个点的图中求一个点使得这个点到其他点的最短路的最长距离最短。 输入数据中有多组测试。每组测试第一行为n接下来n行每行第一个xxi表示第i个点和x个点有路径。接下来x个数对a,b表示i到a的代价为b 最后输出这个点和最长距离。 这道题是显而易见的最短路了。但是我们发现这个题的起点不确定。所以不是单源最短路不能用SPFA 这里介绍另外一种算法floyd算法。 floyd算法主要解决的是多源最短路问题范围比SPFA更广但时间复杂度是O(n^3)。再看题目n≤100符合条件。 floyd算法简而言之就是找i,j两个点然后找一个中间点k如果i-kk-j的最短路径比当前i-j更短就更新i-j的最短路。 代码如下: for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(f[i][j]f[i][k]f[k][j])//f存i-j的最短路{f[i][j]f[i][k]f[k][j];}}}} 最后统计答案时对于每一个点i看看它到其他点的最短路的最大值。这样这道题的代码就呼之欲出了。 参考代码 #includecstdio
#includecstdlib
#includecstring
int n;
int f[105][105];
int main()
{while(1){scanf(%d,n);if(n0)break;memset(f,63,sizeof(f));for(int i1;in;i){f[i][i]0;int x;scanf(%d,x);for(int j1;jx;j){int soy1,soy2;scanf(%d %d,soy1,soy2);f[i][soy1]soy2;}}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(f[i][j]f[i][k]f[k][j]){f[i][j]f[i][k]f[k][j];}}}}/*for(int i1;in;i){for(int j1;jn;j)printf(%d ,f[i][j]10000?-1:f[i][j]);printf(\n);}*/int ans2147483647,ans2-1;for(int i1;in;i){int tt-1;for(int j1;jn;j){if(f[i][j]999999){tt-1;break;}if(f[i][j]tt)ttf[i][j];}if(tt!-1 ttans){anstt;ans2i;}}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
