POJ1125 Floyd
Floyd
2023-09-11 14:13:59 时间
题意:
给你n个点,问你在哪里选择开会地点,使得到所有点的最长路径最短.
给你n个点,问你在哪里选择开会地点,使得到所有点的最长路径最短.
思路: n很小,直接Floyd,然后暴力枚举就行了。
#include<stdio.h>
#define INF 100000000
int map[110][110];
int minn(int a ,int b)
{
return a < b ? a : b;
}
void Floyd(int n)
{
for(int k = 1 ;k <= n ;k ++)
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]);
}
int main ()
{
int n ,i ,j ,nn;
int b ,c;
while(~scanf("%d" ,&n) && n)
{
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
if(i == j) map[i][j] = 0;
else map[i][j] = INF;
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%d" ,&nn);
for(j = 1 ;j <= nn ;j ++)
{
scanf("%d %d" ,&b ,&c);
map[i][b] = c;
}
}
Floyd(n);
int Min = INF ,mk;
for(i = 1 ;i <= n ;i ++)
{
int Max = 0;
for(j = 1 ;j <= n ;j ++)
if(Max < map[i][j])
Max = map[i][j];
if(Max != INF && Min > Max)
{
Min = Max;
mk = i;
}
}
if(Min == INF) printf("disjoint\n");
else printf("%d %d\n" ,mk ,Min);
}
return 0;
}
相关文章
- 【图论——第六讲】Floyd算法求多源最短路问题
- POJ2570 二进制,位运算,Floyd
- POJ2391 Floyd+离散化+二分+DINIC
- 【BZOJ2306】[Ctsc2011]幸福路径 倍增Floyd
- 数据结构 娱乐中心选址 (Floyd+暴力)
- HDU 3665 Seaside (最短路,Floyd)
- Floyd算法与Dijkstra算法的区别
- 【蓝桥杯Java组】最短路径Floyd算法原来如此简单
- ZOJ1221 && UVA567:Risk(Floyd)
- 人活着系列Tanya和蔡健雅猪 (floyd)
- hdu 1385 Minimum Transport Cost (Floyd)
- Floyd算法
- 【loj6177】「美团 CodeM 初赛 Round B」送外卖2 Floyd+状压dp
- 【bzoj2324】[ZJOI2011]营救皮卡丘 最短路-Floyd+有上下界费用流
- 【bzoj1143】[CTSC2008]祭祀river Floyd+网络流最小割