Submission #1296311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296311		alan_c	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	158 ms	16860 KiB

commuter_pass

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

using ll = long long;

const int N = 1e5+1;
vector<pair<int, int>> adj[N];
ll ds[N], du[N], dv[N], minu[N], minv[N], ans[N];

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

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

  while (m--) {
    int a, b, c; cin >> a >> b >> c;
    adj[a].emplace_back(b, c);
    adj[b].emplace_back(a, c);
  }

  auto dijkstra = [&](int start, ll(&dist)[N], bool store = false) {
    for (int i = 1; i <= n; i++)
      dist[i] = 1e18;
    dist[start] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater< >> pq;
    pq.emplace(0, start);
    while(!pq.empty()) {
      auto[d, a] = pq.top();
      pq.pop();
      if(d != dist[a])
        continue;

      if(store)
        ans[a] = min({ans[a], minu[a] + dv[a], minv[a] + du[a]});

      for(auto&[b, c] : adj[a]) {
        ll cost = d + c;
        if(cost < dist[b]) {
          dist[b] = cost;
          pq.emplace(cost, b);

          if(store) {
            minu[b] = min(du[b], minu[a]);
            minv[b] = min(dv[b], minv[a]);
            ans[b] = ans[a];
          }
        } else if(store && cost == dist[b]) {
          minu[b] = min(minu[b], minu[a]);
          minv[b] = min(minv[b], minv[a]);
          ans[b] = min(ans[b], ans[a]);
        }
      }
    }
  };
  dijkstra(u, du);
  dijkstra(v, dv);

  minu[s] = du[s];
  minv[s] = dv[s];
  ans[s] = du[s] + dv[s];
  dijkstra(s, ds, true);

  cout << min(du[v], ans[t]) << '\n';
}

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