fork(2) download
  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
stdin
Standard input is empty
stdout
Standard output is empty