Submission #851632

#	Time	Username	Problem	Language	Result	Execution time	Memory
851632		bean	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	223 ms	14544 KiB

commuter_pass

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

void solve() {
  int n, m;
  cin >> n >> m;
  int s, t;
  cin >> s >> t;
  int u, v;
  cin >> u >> v;
  s--, t--, u--, v--;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    cin >> from >> to >> cost;
    from--, to--;
    g[from].push_back({to, cost});
    g[to].push_back({from, cost});
  }
  auto djikstra = [&](int s) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<>>
        pq;
    vector<long long> d(n, LLONG_MAX);
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
      auto [d_v, from] = pq.top();
      pq.pop();
      if (d_v != d[from]) continue;
      for (auto [to, cost] : g[from]) {
        if (d[to] > d[from] + cost) {
          d[to] = d[from] + cost;
          pq.push({d[to], to});
        }
      }
    }
    return d;
  };
  auto a = djikstra(s);
  auto b = djikstra(t);
  auto c = djikstra(v);
  long long ans = LLONG_MAX, mind = a[t];
  for (int i = 0; i < n; i++) {
    if (a[i] + b[i] == mind) ans = min(ans, c[i]);
  }
  cout << ans;
}

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

  int tt = 1;
  // cin >> tt;

  while (tt--) {
    solve();
  }

  return 0;
}

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