Submission #1083217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083217		bean	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	234 ms	20260 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, m, s, t, u, v;
  cin >> n >> m >> s >> t >> u >> v;
  --s, --t;
  --u, --v;

  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    --x, --y;
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }

  const int64_t inf = 1e18;
  using P = pair<int64_t, int>;

  auto dijkstra = [&](int s) {
    const int64_t inf = int64_t(1e18);
    vector<int64_t> d(n, inf);
    priority_queue<P, vector<P>, greater<>> pq;
    pq.emplace(d[s] = 0, s);
    while (pq.size()) {
      int64_t d_v;
      int v;
      tie(d_v, v) = pq.top();
      pq.pop();
      if (d_v != d[v])
        continue;
      for (auto &it : g[v]) {
        int u = it.first;
        int w = it.second;
        if (d[v] + w < d[u]) {
          pq.emplace(d[u] = d[v] + w, u);
        }
      }
    }
    return d;
  };

  auto du = dijkstra(u);
  auto dv = dijkstra(v);

  auto dijkstra2 = [&](int s, int t) {
    vector<array<int64_t, 2>> dp(n, {inf, inf});
    vector<int64_t> d(n, inf);
    priority_queue<P, vector<P>, greater<>> pq;

    dp[s][0] = du[s];
    dp[s][1] = dv[s];
    pq.emplace(d[s] = 0, s);

    while (pq.size()) {
      int64_t d_v;
      int v;
      tie(d_v, v) = pq.top();
      pq.pop();
      if (d_v != d[v])
        continue;
      for (auto &it : g[v]) {
        int u, w;
        tie(u, w) = it;
        if (d[u] > d[v] + w) {
          dp[u][0] = min(dp[v][0], du[u]);
          dp[u][1] = min(dp[v][1], dv[u]);
          pq.emplace(d[u] = d[v] + w, u);
        } else if (d[u] == d[v] + w) {
          if (min(dp[v][0], du[u]) + min(dp[v][1], dv[u]) <=
              dp[u][0] + dp[u][1]) {
            dp[u][0] = min(dp[v][0], du[u]);
            dp[u][1] = min(dp[v][1], dv[u]);
          }
        }
      }
    }
    return dp[t][0] + dp[t][1];
  };

  int64_t res = du[v];
  res = min(res, dijkstra2(s, t));
  res = min(res, dijkstra2(t, s));
  cout << res;
}

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