Cod sursa(job #653930)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 29 decembrie 2011 11:57:07
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
# include <fstream>
 # include <algorithm>
 # include <vector>
 # include <queue>
 
 # define pb push_back
 # define dim 2001
 # define inf 99999
 
 using namespace std;
 
 struct ubuntu
 {
	 int nod, cost;
 };
 
 vector < int >  t, drum( dim, inf );
 vector < ubuntu > a[ dim ], var;
 queue < int > q;
 
 int n, m, k;
 
 ifstream f("ubuntzei.in");
 ofstream g("ubuntzei.out");
 
 void citire()
 {
	 int i, j, x, y, z;
	 f >> n >> m;
	 f >> k;
	 for ( i = 1 ; i <= k ; i++ )
	 {
		 f >> x;
		 t.pb( x );
	 }
	 for ( i = 1 ; i <= m ; i++ )
	 {
		 f >> x >> y >> z;
		 a[ x ].pb( ( ubuntu ) { y, z } );
		 a[ y ].pb( ( ubuntu ) { x, z } );
	 }
 }
 
 void dijkstra()
 {
	 int i, x, xx;
	 x = 1;
	 drum[ x ] = 0;
	 q.push( x );
	 while ( !q.empty() )
	 {
		 xx = q.front();
		 for( i = 0 ; i < a[ xx ].size() ; i++ )
			 if( drum[ xx ] + a[ xx ][ i ].cost < drum[ a[ xx ][ i ].nod ] )
			 {
			     drum[ a[ xx ][ i ].nod ] =  drum[ xx ] + a[ xx ][ i ].cost;
				 q.push( a[ xx ][ i ].nod );
			 }
			 q.pop();
	 }
 }
 
 void afisare()
 {
	 int i, j;
	 
	/* for ( i = 1 ; i <= n ; i ++ )
	 {
		 for ( j = 0 ; j < a[ i ].size() ; j++ )
			 g << a[ i ][ j ].nod << " ";
		 g << "\n";
	 }
	 g << "\n";
	 for ( i = 1 ; i <= n ; i ++ )
	 {
		 for ( j = 0 ; j < a[ i ].size() ; j++ )
			 g << a[ i ][ j ].cost << " ";
		 g << "\n";
	 }*/
	/* for ( i = 1 ; i <= n ; i++ )
		 g << drum[ i ] << " ";*/
	 g <<drum[ n ];
 }
 
 int main()
 {
	 citire();
	 dijkstra();
	 afisare();
	 return 0;
 }