fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define REP(i, a, b) for (Int i = a; i <= b; i++)
  5. #define FOR(i, n) for (Int i = 0; i < n; i++)
  6. #define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
  7. #define fill(ar, val) memset(ar, val, sizeof(ar))
  8. #define PI 3.1415926535897932385
  9. #define uint64 unsigned long long
  10. #define Int long long
  11. #define int64 long long
  12. #define all(ar) ar.begin(), ar.end()
  13. #define pb push_back
  14. #define ff first
  15. #define mp make_pair
  16. #define ss second
  17. #define bit(n) (1<<(n))
  18. #define Last(i) ( (i) & (-i) )
  19. #define sq(x) ((x) * (x))
  20. const Int inf = 1e15  ;
  21.  
  22. Int d[ 301 ][ 301 ] ;
  23. vector<vector< pair< int, Int > > >g ( 301 ) ;
  24. int n   ;
  25.  
  26. Int djkstra( int s , int e )
  27. {
  28.  
  29.  
  30. 	vector<Int> d (n, inf);
  31. 	d[s] = 0;
  32. 	set < pair<Int,int> > q;
  33. 	q.insert (make_pair (d[s], s));
  34.  
  35. 	while (!q.empty()) {
  36. 		int v = q.begin()->second;
  37. 		q.erase (q.begin());
  38.  
  39. 		for (size_t j=0; j<g[v].size(); ++j) {
  40.  
  41.    int to = g[v][j].first;
  42. 			Int len = g[v][j].second;
  43.  
  44. 			if (d[v] + len < d[to]) {
  45. 				q.erase (make_pair (d[to], to));
  46. 				d[to] = d[v] + len;
  47. 				q.insert (make_pair (d[to], to));
  48. 			}
  49. 		}
  50. 	}
  51.  
  52.     if(  d[e] >= inf ) d[e] = -1 ;
  53. 	return d[e]  ;
  54.  
  55. }
  56. int main ( )
  57.  {
  58.  
  59.  
  60.  	int m , s , e ;
  61.  	cin >> n >> m >> s >>  e ;
  62.  	--s ; --e ;
  63.    FOR(  i  , n )FOR( j ,n  )d[i][j]  = inf ; // memset( d , inf ,  sizeof(d)) ;
  64.  
  65.     FOR( i , m )
  66.      {
  67.          int u , v , w ;
  68.          cin >> u >>  v >>  w ;
  69.          --u ; --v  ;
  70.          d[u][v] = w ;
  71.  
  72.      }
  73.  
  74.     for( int i =  0 ; i <  n ; i ++ )
  75.              d[i][i] =  0 ;
  76.  
  77.     for( int k = 0 ; k < n ; k ++ )
  78.       for( int i = 0 ; i < n ; i ++ )
  79.      	 for( int j = 0 ; j < n ; j ++ )
  80.             {
  81.                        if(  d[i][k] + d[k][j] <  d[i][j] )
  82.                  	      d[i][j] = d[i][k] + d[k][j] ;
  83.  
  84.             }
  85.  
  86.  
  87.      FOR( i , n )
  88.       FOR( j , n )
  89.        {
  90.             if(  d[i][j] < inf && d[j][i] < inf )
  91.             	 {  g[i].pb( mp( j , d[i][j] + d[j][i] ) ) ;
  92.             	    g[j].pb( mp( i , d[i][j] + d[j][i] ) ) ;
  93.                  }
  94.  
  95.  
  96.        }
  97.  
  98.  
  99.      cout << djkstra ( s , e  ) ;
  100.  
  101.  }
  102.  
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
4 5 1 3
1 2 10
2 3 5
2 4 7
3 2 1
4 1 2
stdout
copy 
25
https://ideone.com/zFAPhn
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!