Advertisement
Dennnhhhickk

Untitled

Apr 23rd, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1000000000;
  6.  
  7. int main() {
  8.  
  9. int n, c, x, y, m, s, t, a, b;
  10. cin >> n >> m >> s >> t;
  11. s--;
  12. t--;
  13. vector < vector < pair<int,int> > > g (n);
  14. for (int i = 0; i < m; i++){
  15. cin >> x >> y >> c;
  16. g[x - 1].push_back(pair <int, int> (y - 1, c));
  17. g[y - 1].push_back(pair <int, int> (x - 1, c));
  18. }
  19. cin >> a >> b;
  20. vector<int> d (n, INF), p (n);
  21. d[s] = 0;
  22. set < pair<int,int> > q;
  23. q.insert (make_pair (d[s], s));
  24. while (!q.empty()) {
  25. int v = q.begin()->second;
  26. q.erase (q.begin());
  27.  
  28. for (size_t j=0; j<g[v].size(); ++j) {
  29. int to = g[v][j].first,
  30. len = g[v][j].second;
  31. if (d[v] + len < d[to] && d[v] + len <= a) {
  32. q.erase (make_pair (d[to], to));
  33. d[to] = d[v] + len;
  34. p[to] = v;
  35. q.insert (make_pair (d[to], to));
  36. }
  37. }
  38. }
  39. for (long long i = 0; i < n; i++)
  40. if (d[i] != INF)
  41. q.insert(pair <int, int> (d[i], i));
  42. //vector<int> d (n, INF), p (n);
  43. while (!q.empty()) {
  44. int v = q.begin()->second;
  45. q.erase (q.begin());
  46.  
  47. for (size_t j=0; j<g[v].size(); ++j) {
  48. int to = g[v][j].first,
  49. len = g[v][j].second;
  50. if (d[v] + len < d[to] && d[v] + len >= b) {
  51. q.erase (make_pair (d[to], to));
  52. d[to] = d[v] + len;
  53. p[to] = v;
  54. q.insert (make_pair (d[to], to));
  55. }
  56. }
  57. }
  58. if (d[t] != INF)
  59. cout << d[t];
  60. else
  61. cout << -1;
  62. cout << endl;
  63. return 0;
  64. }
  65.  
  66.  
  67. /*
  68. 4 6
  69. 1 4
  70. 1 2 4
  71. 2 4 4
  72. 4 1 6
  73. 1 3 7
  74. 4 3 10
  75. 3 2 2
  76. 5 6
  77. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement