Submission #1083196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083196		bean	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	78 ms	12952 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 < n; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    --x; --y;
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }

  auto dijkstra = [&](int s) {
    priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<>> pq;
    const int64_t inf = int64_t(1e18);
    vector<int64_t> d(n, inf);
    pq.emplace(d[s] = 0, s);
    while (pq.size()) {
      int64_t d_v;
      int v;
      tie(d_v, v) = pq.top();
      pq.pop();
      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 d_u = dijkstra(u);
  auto d_v = dijkstra(v);

  auto dijkstra2 = [&](int s, int t) {
    const int64_t inf = int64_t(1e18);
    vector<int64_t> dp_u(n, inf), dp_v(n, inf);
    vector<int64_t> d(n, inf);
    priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<>> pq;
    pq.emplace(d[s] = 0, s);
    dp_u[s] = d_u[s];
    dp_v[s] = d_v[s];
    while (pq.size()) {
      int64_t dv;
      int v;
      tie(dv, v) = pq.top();
      pq.pop();
      if (dv != d[v]) continue;
      for (auto &it : g[v]) {
        int u = it.first;
        int w = it.second;
        int64_t nx_u = min(dp_u[v], d_u[u]);
        int64_t nx_v = min(dp_v[v], d_v[u]); 
        if (d[u] > d[v] + w) {
          dp_u[u] = nx_u;
          dp_v[u] = nx_v;
          pq.emplace(d[u] = d[v] + w, u);
        } else if (d[u] == d[v] + w) {
          if (nx_u + nx_v < dp_u[u] + dp_v[v]) {
            dp_u[u] = nx_u;
            dp_v[u] = nx_v;
          }
        }
      }
    }
    return dp_u[t] + dp_v[t];
  };

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

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