Submission #236405

#	Time	Username	Problem	Language	Result	Execution time	Memory
236405		LifeHappen__	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	459 ms	23376 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {return l + rng() % (r - l + 1);}
#define For(a, b, c) for(int a = b, _c = c; a <= _c; ++a)
#define Ford(a, b, c) for(int a = b, _c = c; a >= _c; --a)
#define Forv(a, b) for(auto &a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mt make_tuple
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x, i) (x >> (i - 1) & 1ll)
#define onbit(x, i) (x | (1ll << (i - 1)))
#define offbit(x, i) (x & ~(1ll << (i - 1)))

const int N = 1e5 + 5;
const int INF = 1e15;
int n, m, s, t, u, v;
int dep[N];
vector<ii> ad[N];

void dij(int i, vector<int> &f) {
      fill(all(f), INF);
      priority_queue<ii, vector<ii>, greater<ii>> h;
      h.push({0, i}); f[i] = 0;
      while(h.size()) {
            int c, u; tie(c, u) = h.top(); h.pop();
            if(f[u] != c) continue;
            for(auto vv : ad[u]) {
                  int v, w; tie(v, w) = vv;
                  if(f[v] > f[u] + w) {
                        f[v] = f[u] + w;
                        h.push({f[v], v});
                  }
            }
      }
}

int32_t main() {
      ios_base::sync_with_stdio(false);
      cin.tie(0); cout.tie(0);

      cin >> n >> m;
      cin >> s >> t >> u >> v;
      For(i, 1, m) {
            int x, y, c; cin >> x >> y >> c;
            ad[x].pb({y, c});
            ad[y].pb({x, c});
      }

      vector <int> fs(n + 1), ft(n + 1), fu(n + 1), fv(n + 1);
      dij(s, fs);
      dij(t, ft);
      dij(u, fu);
      dij(v, fv);

      int ans = fu[v];
      For(w, 0, 1) {
            vector <int> f(n + 1, INF), pf(n + 1, INF);
            priority_queue<ii, vector<ii>, greater<ii>> h;
            h.push({0, s});
            f[s] = 0;
            pf[s] = fu[s];
            while(h.size()) {
                  int u, w;
                  tie(w, u) = h.top();
                  h.pop();
                  ans = min(ans, pf[u] + fv[u]);
                  Forv(v, ad[u]) {
                        if(fs[v.fi] + ft[v.fi] == fs[t]) {
                              pf[v.fi] = min({pf[v.fi], fu[v.fi], pf[u]});
                              if(f[v.fi] > w + v.se) {
                                    f[v.fi] = w + v.se;
                                    h.push({f[v.fi], v.fi});
                              }
                        }
                  }
            }
            swap(fv, fu);
      }
      cout << ans << '\n';

}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45