学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1595

求最短路中间的最长路径

题意为求最短路，但是要求的是最短路中间当去掉某一条路时的情况下路径最长的，这里是使用Dijkstra写的，代码相较其他简便了很多，值得注意的是当记录路径时，当传入的v0为0 时不要记录

#include<iostream>
#include<cstdio>
#include<cstring>
const int INF = 1000000000 ;
const int maxn = 1005 ;
int edge[ maxn ][ maxn ] ;
int path[ maxn ] ;
int used[ maxn ] ;
int dist[ maxn ] ;
int n , m ;

int Dijkstra( int v0 )
{
	int  i , j , k ;
	memset( used , 0 , sizeof( used ) ) ;
	for( i = 0 ; i <= n ; i++ ) 
	{
		dist[ i ] = INF ;
	}
	dist[ 1 ] = 0 ;
	for( i = 1 ; i <= n ; i++ )
	{
		int MIN = INF , u = v0 ;
		for( j = 1 ; j <= n ; j++ )
		{
			if( !used[ j ] && dist[ j ] < MIN )
			{
				MIN = dist[ j ] ;
				u = j ;
			}
		}
		used[ u ] = 1 ;
		for( k = 1 ; k <= n ; k++ )
		{
			if( !used[ k ] && edge[ u ][ k ] && edge[ u ][ k ] + dist[ u ] < dist[ k ] )
			{
				dist[ k ] = dist[ u ] + edge[ u ][ k ] ;
				if( v0 )
					path[ k ] = u ;
			}
		}
	}
}


int main()
{
	int i , j , k ;
	int x , y , temp ;
	while( scanf( "%d%d" , &n ,&m ) != EOF )
	{
		memset( edge , 0 , sizeof( edge ) ) ;
		for( i = 1 ; i <= n ; i++ )
		{
			for( j = 1 ; j <= n ; j++ )
			{
				if( i == j )
					edge[ i ][ j ] = 0 ;
				else
					edge[ i ][ j ] = INF ;
			}
		}
		memset( path , 0 , sizeof( path ) ) ;
		for( i = 0 ; i < m ; i++ )
		{
			scanf( "%d%d%d" , &x, &y , &temp ) ;
			if( temp < edge[ x ][ y ] )
				edge[ x ][ y ] = edge[ y ][ x ] = temp ;
		}
		Dijkstra( 1 ) ;
		int MAX = dist[ n ] ;
		for( i = n ; i != 1 ; i = path[ i ] )
		{
			int t = edge[ path[ i ] ][ i ] ;
			edge[ path[ i ] ][ i ] = INF ;
			edge[ i ][ path[ i ] ] = INF ;
			Dijkstra( 0 ) ; 
			
			if( dist[ n ] > MAX )
				MAX = dist[ n ] ;
			edge[ i ][ path[ i ] ] = edge[ path[ i ] ][ i ] = t ;
		}
		printf( "%d\n" , MAX ) ;
	}
	return 0 ;
}