fork(2) download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long int ll;
  6. typedef long double ld;
  7. typedef vector<ll> vl;
  8. typedef queue<ll> ql;
  9. typedef set<ll> sl;
  10. typedef vector<int> vi;
  11. typedef queue<int> qi;
  12. typedef set<int> si;
  13.  
  14. #define pb push_back
  15. #define lb lower_bound
  16. #define ub upper_bound
  17. #define mp make_pair
  18. #define fr(i, a, b) for(i=a; i<b; i++)
  19. #define mset(a, b) memset(a, b, sizeof(a))
  20. #define mcpy(a, b) memcpy(a, b, sizeof(a))
  21. #define sortv(a) sort(a.begin(), a.end())
  22. #define max(x, y) ((x) > (y) ? (x) : (y))
  23. #define min(x, y) ((x) < (y) ? (x) : (y))
  24. #define sqr(x) ((x) * (x))
  25. #define sz(x) ((ll)x.size())
  26.  
  27. #define trace1(x)							cerr << #x << ": " << x << endl;
  28. #define trace2(x, y)						cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  29. #define trace3(x, y, z)						cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  30. #define trace4(a, b, c, d)       			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  31. #define trace5(a, b, c, d, e)    			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  32. #define trace6(a, b, c, d, e, f) 			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  33.  
  34. int i=0;
  35. int t, n, m, k, s, d, u, v, length, upto, ans;
  36.  
  37. struct node{
  38. 	int v, d;
  39. 	node(int a, int b){
  40. 		v=a; d=b;
  41. 	}
  42. };
  43.  
  44. vector<node> adj[10001], rev[10001];
  45. int da[10001], db[10001];
  46.  
  47. int main(){
  48. 	scanf("%d", &t);
  49. 	while(t--){
  50. 		scanf("%d%d%d%d%d", &n, &m, &k, &s, &d);
  51. 		fr(i, 0, n){
  52. 			da[i]=INT_MAX;
  53. 			db[i]=INT_MAX;
  54. 			adj[i].clear();
  55. 			rev[i].clear();
  56. 		}
  57. 		fr(i, 0, m){
  58. 			scanf("%d%d%d", &u, &v, &length);
  59. 			u--; v--;
  60. 			adj[u].pb(node(v, length));
  61. 			rev[v].pb(node(u, length));
  62. 		}
  63. 		set<pair<int, int> > q;
  64. 		s--; d--;
  65. 		q.insert(mp(0, s));
  66. 		while(!q.empty()){
  67. 			u=q.begin()->second;
  68. 			upto=q.begin()->first;
  69. 			q.erase(q.begin());
  70. 			fr(i, 0, sz(adj[u])){
  71. 				v=adj[u][i].v;
  72. 				length=adj[u][i].d;
  73. 				if(upto+length<da[v]){
  74. 					q.erase(mp(da[v], v));
  75. 					da[v]=upto+length;
  76. 					q.insert(mp(da[v], v));
  77. 				}
  78. 			}
  79. 		}
  80. 		q.insert(mp(0, d));
  81. 		while(!q.empty()){
  82. 			u=q.begin()->second;
  83. 			upto=q.begin()->first;
  84. 			q.erase(q.begin());
  85. 			fr(i, 0, sz(rev[u])){
  86. 				v=rev[u][i].v;
  87. 				length=rev[u][i].d;
  88. 				if(upto+length<db[v]){
  89. 					q.erase(mp(db[v], v));
  90. 					db[v]=upto+length;
  91. 					q.insert(mp(db[v], v));
  92. 				}
  93. 			}
  94. 		}
  95. 		ans=db[s];
  96. 		fr(i, 0, k){
  97. 			scanf("%d%d%d", &u, &v, &length);
  98. 			u--; v--;
  99. 			if(da[u]!=INT_MAX && db[v]!=INT_MAX){
  100. 				ans=min(ans, da[u]+length+db[v]);
  101. 			}
  102. 			if(da[v]!=INT_MAX && db[u]!=INT_MAX){
  103. 				ans=min(ans, da[v]+length+db[u]);
  104. 			}
  105. 		}
  106. 		if(ans==INT_MAX){
  107. 			printf("-1\n");
  108. 			continue;
  109. 		}
  110. 		printf("%d\n", ans);
  111. 	}
  112. }
  113.  
Success #stdin #stdout 0s 3656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2EK3e8
language:
C++ (gcc 8.3)
created:
9 years 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!