#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") ;
} |