Submission #1287492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287492		kunzaZa183	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	358 ms	19228 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
  int n, m;
  cin >> n >> m;
  int s, t, u, v;
  cin >> s >> t >> u >> v;
  s--, t--, u--, v--;

  vector<vector<pair<int, int>>> vvpii(n);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    vvpii[a].emplace_back(b, c), vvpii[b].emplace_back(a, c);
  }

  const int bign = 1e18;
  auto dijkstra = [&](int dest) {
    vector<int> shortest(n, bign);

    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pqpii;
    pqpii.emplace(0, dest);

    while (!pqpii.empty()) {
      auto [val, in] = pqpii.top();
      pqpii.pop();

      if (shortest[in] != bign)
        continue;

      shortest[in] = val;

      for (auto [to, w] : vvpii[in])
        if (shortest[to] == bign) {
          pqpii.emplace(w + val, to);
        }
    }

    return shortest;
  };

  vector<int> froms = dijkstra(s), fromu = dijkstra(u), fromv = dijkstra(v);
  vector<int> changeu(fromu), changev(fromv);

  vector<int> vi(n);
  iota(vi.begin(), vi.end(), 0);
  sort(vi.begin(), vi.end(), [&](int a, int b) { return froms[a] > froms[b]; });

  vector<int> partofit(n);

  partofit[t] = 1;

  int ans = fromu[v];
  for (auto a : vi) {

    for (auto [to, w] : vvpii[a]) {
      if (froms[to] == froms[a] + w && partofit[to] == 1) {
        partofit[a] = 1;
        changev[a] = min(changev[a], changev[to]);
        changeu[a] = min(changeu[a], changeu[to]);
      }
    }

    if (partofit[a])
      ans = min({ans, fromu[a] + changev[a], fromv[a] + changeu[a]});
  }

  cout << ans << "\n";
}

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