Advertisement
Guest User

B

a guest
Apr 6th, 2019
348
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <set>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. const int N = 50;
  11.  
  12. vector<pair<int, int>> a[N];
  13.  
  14. int d[2019][N];
  15.  
  16. const int oo = 50 * 2019 * 1000;
  17.  
  18. int n, m, s, t;
  19.  
  20. set<pair<int, pair<int, int>>> pending;
  21.  
  22. void update(int remainder, int vertex, int distance) {
  23.   if (d[remainder][vertex] > distance) {
  24.     d[remainder][vertex] = distance;
  25.     pending.insert(make_pair(distance, make_pair(remainder, vertex)));
  26.   }
  27. }
  28.  
  29. pair<int, int> pop() {
  30.   auto x = *pending.begin();
  31.   pending.erase(pending.begin());
  32.   return x.second;
  33. }
  34.  
  35. int main() {
  36.   cin >> n >> m >> s >> t;
  37.   assert(0 < n && n <= 50);
  38.   assert(0 <= m && m <= 2000);
  39.   assert(0 < s && s <= n);
  40.   assert(0 < t && t <= n);
  41.   s--;
  42.   t--;
  43.   for (int i = 0; i < m; i++) {
  44.     int x, y, l;
  45.     cin >> x >> y >> l;
  46.     assert(0 < x && x <= n);
  47.     assert(0 < y && y <= n);
  48.     assert(0 < l && l <= 1000);
  49.     x--;
  50.     y--;
  51.     a[x].push_back(make_pair(y, l));
  52.     a[y].push_back(make_pair(x, l));
  53.   }
  54.  
  55.   for (int i = 0; i < 2019; i++)
  56.     for (int j = 0; j < n; j++) {
  57.       d[i][j] = oo;
  58.     }
  59.   update(1, s, 0);
  60.   while (!pending.empty()) {
  61.     auto cur = pop();
  62.     int remx = cur.first;
  63.     int remy = (remx + 1) % 2019;
  64.     int x = cur.second;
  65.     int dx = d[remx][x];
  66.     for (auto yl : a[x]) {
  67.       update(remy, yl.first, dx + yl.second);
  68.     }
  69.   }
  70.   if (d[0][t] == oo) {
  71.     cout << "Mumkun emes" << endl;
  72.   } else {
  73.     cout << d[0][t] << endl;
  74.   }
  75.   return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement