hdu 5137 去掉一个点 使得最短路最大(2014广州现场赛 K题)

时间:2022-07-31 21:30:49

题意:从2~n-1这几个点中任意去掉一个点,使得从1到n的最短路径最大,如果任意去掉一个点1~n无通路输出Inf。

Sample Input
4 5
1 2 3
1 3 7
1 4 50
2 3 4
3 4 2
3 2
1 2 30
2 3 10
0 0

Sample Output
50
Inf

 # include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <string>
# include <map>
# include <cmath>
# include <queue>
# include <list>
# define LL long long
using namespace std ; const int MAXN=;
const int INF=0x3f3f3f3f;
int n , m ;
bool vis[MAXN];
int cost[MAXN][MAXN] ;
int lowcost[MAXN] ; void Dijkstra(int beg)
{
for(int i=;i<n;i++)
{
lowcost[i]=INF;
}
lowcost[beg]=;
for(int j=;j<n;j++)
{
int k=-;
int Min=INF;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[i]<Min)
{
Min=lowcost[i];
k=i;
}
if(k==-)
break ;
vis[k]=true;
for(int i=;i<n;i++)
if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
{
lowcost[i]=lowcost[k]+cost[k][i];
}
} } int main ()
{
//freopen("in.txt","r",stdin) ;
while (scanf("%d %d" , &n , &m) !=EOF)
{
if (n == && m == )
break ; int u , v , w ;
int i , j ;
int MAX = ;
for (i = ; i < n ; i++)
for (j = ; j < n ; j++)
{
if (i == j)
cost[i][j] = ;
else
cost[i][j] = INF ;
}
while(m--)
{
scanf("%d%d%d" , &u , &v , &w) ;
cost[u-][v-] = w ;
cost[v-][u-] = w ; } for (i = ; i <= n- ; i++)
{
memset(vis , , sizeof(vis)) ;
vis[i] = ;
Dijkstra() ;
if (lowcost[n-] > MAX )
MAX = lowcost[n-] ; } if (MAX == INF)
printf("Inf\n") ;
else
printf("%d\n" , MAX) ;
} return ;
}