蔡昀修

#include<iostream>
#include<fstream>

using namespace std ;

int main()
{
    ifstream fin("pa.in") ;
   
    int v,w ;
    fin >> v >> w ;
    int map[v][v] ;
    int parent[v] ;
    int visit[v] ;
    int d[v] ;
    const int M = 9999 ; // far   
   
    // init map and draw map
    for( int i = 0 ; i < v ; i ++ )
    {
        for( int j = 0 ; j < v ; j ++ )     
        {
            map[i][j] = M ;     
        }
        visit[i] = false ;
        d[i] = M ;
    }
   
    for( int i = 0 ; i < w ; i ++ )
    {
        int a,b,c ;
        fin >> a >> b >> c ;
        map[a][b] = c ;
        map[b][a] = c ;   
    }

/*    for( int i = 0 ; i < v ; i ++ )
    {
        for( int j = 0 ; j < v ; j ++ )     
        {
            cout << map[i][j] << "\t" ;     
        }
        cout << endl ;
    }*/
                     
    // dijkstra
    d[0] = 0 ;
    parent[0] = 0 ;
    for( int i = 0 ; i < v ; i ++ )
    {
         int min = M ;
         int index = -1 ;
         for( int j = 0 ; j < v ; j ++ )
         {
             if( !visit[j] && d[j] < min )
             {
                 min = d[j] ;
                 index = j ;
             }     
         }
         
         if( index == -1 ) break ;
         visit[index] = true ;
         for( int j = 0 ; j < v ; j ++ )
         {
             if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
             {
                 d[j] = d[index] + map[index][j] ;
                 parent[j] = index ;                    
   
             }
         }   
    }
   
    for( int i = 1 ; i < v ; i ++ )
    {
        cout << i << "->" ;         
        int pre = i ;
        while( parent[pre] != pre )
        {
           pre = parent[pre] ;
           cout << pre << "->" ;
        }
        cout << "cost" << d[i] << endl ;
    }
   
   
    system("Pause") ;
}