Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. /* Murad Eynizade */
  2.  
  3. #include <bits/stdc++.h>
  4. #define int long long
  5. #define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
  6. #define F first
  7. #define S second
  8.  
  9. using namespace std;
  10.  
  11. const int sz = 1001;
  12.  
  13. int n , m , x , y , w , s , t , used[sz][3] , d[sz][3];
  14.  
  15. vector< pair<int,int> >v[sz][3];
  16.  
  17. bool f = false;
  18.  
  19. priority_queue< pair<int,int> >pq;
  20.  
  21. void dijkstra(int s,int di) {
  22. for (int i = 1;i<=n;i++)d[i][di] = 1000000000000000LL;
  23. d[s][di] = 0;
  24. pq.push({0 , s});
  25. while (!pq.empty()) {
  26. int u = pq.top().S;
  27. pq.pop();
  28. for (auto to : v[u][di]) {
  29. if (d[to.F][di] > d[u][di] + to.S) {
  30. d[to.F][di] = d[u][di] + to.S;
  31. pq.push({-d[to.F][di] , to.F});
  32. }
  33. }
  34. }
  35. }
  36.  
  37. void dfs(int s,int di) {
  38. if (f)return;
  39. if (s == t)return;
  40. used[s][di] = 1;
  41. for (auto to : v[s][di]) {
  42. if (f)return;
  43. if (d[to.F][di] < d[s][di]) {
  44. assert(s != t);
  45. if (used[to.F][3 - di] == 1 && to.F != t) {
  46. f = true;
  47. return;
  48. }
  49. if (used[to.F][3 - di] == 0)dfs(to.F , 3 - di);
  50. }
  51. }
  52. used[s][di] = 2;
  53. }
  54.  
  55. int ans[sz][3];
  56.  
  57. int solve(int s,int di) {
  58. if (ans[s][di] != -1)return ans[s][di];
  59. int mx = -1000000000000000LL;
  60. for (auto to : v[s][di]) {
  61. if (d[to.F][di] < d[s][di]) mx = max(mx , to.S + solve(to.F , 3 - di));
  62. }
  63. ans[s][di] = mx;
  64. return mx;
  65. }
  66.  
  67. main()
  68. {
  69. FAST_READ;
  70. cin>>n>>s>>t;
  71. cin>>m;
  72. while (m--) {
  73. cin>>x>>y>>w;
  74. if (x == y)continue;
  75. v[x][1].push_back({y,w});
  76. v[y][1].push_back({x,w});
  77. }
  78. cin>>m;
  79. while (m--) {
  80. cin>>x>>y>>w;
  81. if (x == y)continue;
  82. v[x][2].push_back({y,w});
  83. v[y][2].push_back({x,w});
  84. }
  85. dijkstra(t , 1);
  86. dijkstra(t , 2);
  87. dfs(s , 1);
  88. if (f) {
  89. cout<<-1<<endl;
  90. exit(0);
  91. }
  92. memset(ans , -1 , sizeof(ans));
  93. ans[t][1] = ans[t][2] = 0;
  94. cout<<solve(s , 1)<<endl;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement