Submission #848011

#	Time	Username	Problem	Language	Result	Execution time	Memory
848011		Derek0	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	434 ms	31980 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define overload4(a, b, c, d, name, ...) name
#define rep1(i, n) for(ll i = 0; i < (n); ++i)
#define rep2(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i, n) for(ll i = (n) - 1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (b) - 1; i >= a; --i)
#define per3(i, a, b, c) for(ll i = (b) - 1; i >= (a); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define pb emplace_back
#define lb(v,k) (ll) (lower_bound(all(v), (k)) - v.begin())
#define ub(v,k) (ll) (upper_bound(all(v), (k)) - v.begin())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T, vector<T>, greater<T>>
typedef long long ll;
typedef pair<ll,ll> P;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<P>;
using vvp = vector<vp>;

constexpr ll inf = (ll) 1e18;

constexpr int _ = 100010;

ll n, m, s, t, u, v;
ll deg[_], mn[_][2];
vp g[_];
vi adj[_];

vi Dijkstra(ll s) {
  SPQ(P) h; h.emplace(0, s);
  vi dist(n, -1);
  while (!h.empty()) {
    auto [d, x] = h.top(); h.pop();
    if (dist[x] != -1) continue;
    dist[x] = d;
    for (auto [y, w] : g[x]) {
      h.emplace(d + w, y);
    }
  }
  return dist;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;

  cin >> s >> t >> u >> v;
  --s; --t; --u; --v;

  rep(i, m) {
    ll a, b, c; cin >> a >> b >> c; --a; --b;
    g[a].pb(b, c); g[b].pb(a, c);
  }

  auto ds = Dijkstra(s);
  auto dt = Dijkstra(t);
  auto du = Dijkstra(u);
  auto dv = Dijkstra(v);

  rep(x, n) for (auto [y, w] : g[x]) {
    if (ds[x] + dt[y] + w == ds[t]) {
      adj[x].pb(y);
      deg[y]++;
    }
  }

  rep(i, n) mn[i][0] = mn[i][1] = inf;

  queue<ll> q;
  rep(i, n) if (deg[i] == 0) {
    q.push(i);
    mn[i][0] = du[i];
    mn[i][1] = dv[i];
  }

  ll ans = inf;
  while (!q.empty()) {
    ll x = q.front(); q.pop();
    ans = min(ans, du[x] + dv[x]);
    for (ll y : adj[x]) {
      ll c1 = mn[x][0] + dv[y];
      ll c2 = mn[x][1] + du[y];
      ans = min({ans, c1, c2});
      mn[y][0] = min({mn[y][0], mn[x][0], du[y]});
      mn[y][1] = min({mn[y][1], mn[x][1], dv[y]});
      if (--deg[y] == 0) q.push(y);
    }
  }

  cout << ans << '\n';

  return 0;
}

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