Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cassert>
- #include <cstdio>
- #include <iostream>
- #include <set>
- #include <vector>
- using namespace std;
- const int N = 50;
- vector<pair<int, int>> a[N];
- int d[2019][N];
- const int oo = 50 * 2019 * 1000;
- int n, m, s, t;
- set<pair<int, pair<int, int>>> pending;
- void update(int remainder, int vertex, int distance) {
- if (d[remainder][vertex] > distance) {
- d[remainder][vertex] = distance;
- pending.insert(make_pair(distance, make_pair(remainder, vertex)));
- }
- }
- pair<int, int> pop() {
- auto x = *pending.begin();
- pending.erase(pending.begin());
- return x.second;
- }
- int main() {
- cin >> n >> m >> s >> t;
- assert(0 < n && n <= 50);
- assert(0 <= m && m <= 2000);
- assert(0 < s && s <= n);
- assert(0 < t && t <= n);
- s--;
- t--;
- for (int i = 0; i < m; i++) {
- int x, y, l;
- cin >> x >> y >> l;
- assert(0 < x && x <= n);
- assert(0 < y && y <= n);
- assert(0 < l && l <= 1000);
- x--;
- y--;
- a[x].push_back(make_pair(y, l));
- a[y].push_back(make_pair(x, l));
- }
- for (int i = 0; i < 2019; i++)
- for (int j = 0; j < n; j++) {
- d[i][j] = oo;
- }
- update(1, s, 0);
- while (!pending.empty()) {
- auto cur = pop();
- int remx = cur.first;
- int remy = (remx + 1) % 2019;
- int x = cur.second;
- int dx = d[remx][x];
- for (auto yl : a[x]) {
- update(remy, yl.first, dx + yl.second);
- }
- }
- if (d[0][t] == oo) {
- cout << "Mumkun emes" << endl;
- } else {
- cout << d[0][t] << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement