daily pastebin goal
46%
SHARE
TWEET

Untitled

a guest Nov 17th, 2018 73 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  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. OK, I Understand
 
Top