http://acm.hdu.edu.cn/showproblem.php?pid=2544
Dijkstra模版题,Dijkstra模版终于初步确定了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std ; const int INF = 1000000 ; const int maxn = 105 ; int edge[ maxn ][ maxn ] ; int used[ maxn ] ; int path[ maxn ] ; int dist[ maxn ] ; int S[ maxn ] ; int n , m ; int Dijkstra( int v0 ) { int i , j , k ; memset( used , 0 , sizeof( used ) ) ; for( i = 1 ; i <= n ; i++ ) { dist[ i ] = INF ; } dist[ v0 ] = 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 ] ; } } } } int main() { int x , y , temp ; int i , j , k ; while( scanf( "%d%d" , &n , &m ) != EOF && ( n + m ) ) { memset( edge , 0 , sizeof( edge ) ) ; for( i = 1 ; i <= m ; i++ ) { scanf( "%d%d%d" , &x, &y , &temp ) ; edge[ x ][ y ] = edge[ y ][ x ] = temp ; } Dijkstra( 1 ) ; printf( "%d\n" , dist[ n ] ) ; } }