• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Nov 17th, 2018 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <set>
5. #include <queue>
6. #include <map>
7. #include <string>
8. #include <fstream>
9. #include <stack>
10.
11. using namespace std;
12. typedef long long ll;
13. #define forn(i, n) for (ll i = 0; i < n; i++)
14. #define forna(i, a, n) for (ll i = a; i < n; i++)
15. #define rforn(i, n) for (ll i = n - 1; i >= 0; i--)
16. #define mp(a, b) make_pair(a, b)
17. #define pb(a) push_back(a)
18.
19. struct ed {
20.     ll from, to, weight;
21.
22.     ed(ll a, ll b, ll c) : from(a), to(b), weight(c) {};
23. };
24.
25. int main() {
26.     ios::sync_with_stdio(0);
27.     cin.tie(0);
28.     ll n, m;
29.     cin >> n >> m;
30.     ll _cost = 0;
31.     vector<vector<pair<ll, ll>>> edge(n);
32.     forn(i, m) {
33.         ll q, w, e;
34.         cin >> q >> w >> e;
35.         q--;
36.         w--;
37.         edge[q].pb(mp(w, e));
38.         edge[w].pb(mp(q, e));
39.         if (q == 0 || q == n - 1) {
40.             _cost = e;
41.         }
42.     }
43.     ll t;
44.     cin >> t;
45.     vector<vector<ll>> d(n, vector<ll>(2 * _cost, 2e18));
46.     vector<vector<bool>> was(n, vector<bool>(2 * _cost, false));
47.     set<pair<ll, pair<ll, ll>>> ver;
48.     forn(i, n) {
49.         forn(j, 2 * _cost) {
50.             ver.insert(mp(d[i][j], mp(i, j)));
51.         }
52.     }
53.     d[0][0] = 0;
54.     ll i = 0;
55.     ll j = 0;
56.     while (!ver.empty()) {
57.         was[i][j] = true;
58.         ver.erase(mp(d[i][j], mp(i, j)));
59.         // тут какой-то фор с релаксацией
60.         for (auto _next : edge[i]) {
61.             ll weight = _next.second;
62.             ll kuda = _next.first;
63.             ll ostatok = (j + weight) % (2 * _cost);
64.             if (d[kuda][ostatok] > d[i][j] + weight) {
65.                 ver.erase(mp(d[kuda][ostatok], mp(kuda, ostatok)));
66.                 ver.insert(mp(d[i][j] + weight, mp(kuda, ostatok)));
67.                 d[kuda][ostatok] = d[i][j] + weight;
68.             }
69.         }
70.
71.         i = ver.begin()->second.first;
72.         j = ver.begin()->second.second;
73.     }
74.     cout << (d[n - 1][t % (2 * _cost)] <= t ? "Possible" : "Impossible");
75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top