fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define piint pair < int , int >
  10. #define FOR( i , a , b ) for (int i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define pb push_back 
  12. #define str string 
  13. #define ALL(a) (a).begin() , (a).end() 
  14. #define rep( i , a , b) for (int i = (a) ; i < (b) ; i ++ )
  15. #define ld long double
  16. const int maxn = 1e4;
  17. #define debug 0
  18. #define oo (ll)(1e18)
  19.  
  20. #define pLL pair < ll , ll >  
  21. struct tr
  22. {
  23. 	ll du ;
  24. 	int u , id ; 
  25. };
  26. ll n , m , s , t , k ;
  27. vector < pLL > a[303][maxn+3] ;
  28. ll d[303][maxn+3];
  29. struct cmp {
  30. 	bool operator() (const tr& a , const tr& b ){
  31. 		return a.du > b.du ; 
  32. 	}
  33. } ;
  34. //um , ta se duyet all con truoc , va se add them voi moi con i 
  35. // o ( 6000 * ( (n + m) * (log n ))) 
  36. void JQK ( int st , int ed) {
  37. 	FOR ( i , 0 , k )
  38. 	FOR ( j , 1 , n )
  39. 	d[i][j] = oo ;
  40. 	FOR ( i , 0 , k )
  41. 	d[i][st] = 0 ;
  42. 	priority_queue < tr , vector < tr > , cmp > pq;
  43. 	// priority_queue < pLL , vector < pLL > , greater< pLL > > pq_2 ; 
  44. 	// pq_2.push ({d[0][st] , st }) ;
  45. 	pq.push( { d[0][st] , st , 0 }) ;
  46. 	while (pq.size()){
  47. 		auto [du , u , id ] = pq.top() ;
  48. 		pq.pop() ;
  49. 		if ( du > d[id][u] ) continue ; 
  50. 		// for (auto [v,val] : a[0][u]){
  51. 		// 	if ( d[0][v] > d[0][u] + val ){
  52. 		// 		d[0][v] = d[0][u] + val ;
  53. 		// 		if (debug){
  54. 		// 			cout << "d[0][" << v << "] = :" << d[0][v] << " : = v0 = " << ' ' << v << " : U = : " << u<< '\n'; 
  55. 		// 		}
  56. 		// 		pq.push ( { d[0][v] , v , id }) ; 
  57. 		// 	}
  58. 		// }
  59. 		// neu duong cua id dang duoc su dung thi 
  60. 		// -> hay chieu cua no cung se co co hoi duoc tan dung tren duong di
  61. 		// -> tuc la voi moi con duong a[0] de co th
  62. 		for (auto [v,val] : a[0][u]){
  63. 			if ( d[0][v] > d[id][u] + val ){
  64. 				d[0][v] = d[id][u] + val ;
  65. 				if (debug){
  66. 					cout << "d[0][" << v << "] = :" << d[0][v] << " : = v = " << ' ' << v << ' ' << "id = :" << id << " : U = : " << u<< '\n'; 
  67. 				}
  68. 				pq.push ( { d[0][v] , v , 0 }) ; 
  69. 			}
  70. 		}
  71. 		bool ok = 1 ;
  72. 		if (ok){
  73. 			FOR ( i , 0 , k ){
  74. 				for (auto [v,val] : a[i][u]){
  75. 					if ( d[i][v] > d[0][u] + val ){
  76. 						d[i][v] = d[0][u] + val ;
  77. 						if (debug){
  78. 							cout << "d["<< i<< "][" << v << "] = :" << d[i][v] << " : = v = " << ' ' << v << ' ' << "id = :" << i  << " : U = : " << u<< '\n'; 
  79. 						}
  80. 						pq.push ( { d[i][v] , v , i }) ; 
  81. 					}
  82. 				}
  83. 			}
  84. 		}
  85. 	}
  86. }
  87. ll u , v , w ; 
  88. void input(){
  89. 	int q ; cin >> q;
  90. 	while (q -- ){
  91. 		cin >> n >> m >> k >> s >> t ;
  92. 		FOR ( i , 0 , k )
  93. 		FOR ( j , 1 , n ) a[i][j].clear() ;
  94. 		FOR ( i , 1 , m ){
  95. 			cin >> u >> v >> w ;
  96. 			a[0][u].pb ({ v , w}) ;  
  97. 		}
  98. 		FOR ( i , 1 , k ){
  99. 			cin >> u >> v >> w ; 
  100. 			a[i][u].pb ({ v , w }) ;
  101. 			a[i][v].pb ({ u , w }) ;
  102. 		}
  103. 		JQK( s , t ) ;
  104. 		ll res = oo ;
  105. 		FOR ( i , 0 , k ) res = min ( res , d[i][t]) ;
  106. 		if (res == oo) cout << -1 << '\n';
  107. 		else cout << res << '\n' ;
  108. 	}
  109. 	// 4 DAM ac pls
  110. }
  111. #define name "Traffic Network" 
  112. int main(){
  113.     fast 
  114.     if(fopen(name".INP","r")) {
  115.         freopen (name".INP","r",stdin);
  116.         freopen (name".OUT","w",stdout);
  117.     }
  118.     input() ;
  119.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  120.     return(0) ;
  121. }
Success #stdin #stdout #stderr 0.02s 75260KB
comments (?)
stdin
copy 
1
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25
stdout
copy 
35
stderr
copy 
TIME: = 0.01699
https://ideone.com/IEMrCu
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

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!