Submission #1128355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128355		m_bezrutchka	Commuter Pass (JOI18_commuter_pass)	C++20	55 / 100	2098 ms	94336 KiB

commuter_pass

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

#define int long long

typedef pair<int, int> pii;
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<pii, pii> ppp;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const int LLINF = 2e18 + 10;

const int MAXN = 2e5 + 10;

int n;
vector<pii> adj[MAXN];

vector<int> dijkstra(vector<int> &start_distances) {
  vector<int> dist(n + 1);
  vector<int> mrk(n + 1, false);
  priority_queue<pii> pq;
  for (int i = 1; i <= n; i++) {
    dist[i] = start_distances[i];
    pq.push({-dist[i], i});
  }
  while (!pq.empty()) {
    int v = pq.top().second;
    pq.pop();
    if (mrk[v]) continue;
    mrk[v] = true;
    for (auto [w, c]: adj[v]) {
      if (!mrk[w] && dist[w] > dist[v] + c) {
        dist[w] = dist[v] + c;
        pq.push({-dist[w], w});
      }
    }
  }
  return dist;
}

vector<int> commuter_pass(
  vector<int> &start_distances,
  vector<int> &dh,
  vector<int> &ds,
  int school) {
  map<pii, int> dist;
  set<pii> mrk;
  priority_queue<ppp> pq;
  vector<bool> in_path(n + 1, false);
  for (int i = 1; i <= n; i++) {
    int start_dist;
    if (dh[i] + ds[i] == dh[school]) {
      start_dist = start_distances[i];
      in_path[i] = true;
    } else {
      start_dist = LLINF;
    }
    dist[{i, 0}] = start_dist;
    pq.push({{-start_dist, -start_dist}, {i, 0}});
  }
  for (int v = 1; v <= n; v++) {
    for (auto [w, c]: adj[v]) {
      dist[{w, v}] = LLINF;
      pq.push({{-LLINF, -LLINF}, {v, w}});      
    }
  }

  while (!pq.empty()) {
    ppp x = pq.top();
    int d = -x.first.first;
    int cp = -x.first.second;
    int v = x.second.first;
    int p = x.second.second;
    pq.pop();
    if (d == LLINF || mrk.count({v, p})) continue;
    mrk.insert({v, p});
    
    for (auto [w, c]: adj[v]) {
      if ((p == 0 && in_path[w]) || dh[p] + cp + c + ds[w] == dh[school] || ds[p] + cp + c + dh[w] == dh[school]) {
        int dold = dist[{w, v}];
        int dnew = dist[{v, p}];
        if (!mrk.count({w, v}) && dold > dnew) {
          dist[{w, v}] = dnew;
          pq.push({{-dnew, -c}, {w, v}});
        }
      }
    }
  }

  vector<int> ret(n + 1, LLINF);
  for (auto [k, val]: dist) {
    ret[k.first] = min(ret[k.first], val);
  }
  return ret;
}

void solve() {
  int m, house, school, book_u, book_v;
  cin >> n >> m >> house >> school >> book_u >> book_v;
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }

  vector<int> dists(n + 1, LLINF);

  dists[house] = 0;
  vector<int> d_house = dijkstra(dists);

  dists[house] = LLINF;
  dists[school] = 0;
  vector<int> d_school = dijkstra(dists);

  dists[school] = LLINF;
  dists[book_u] = 0;
  vector<int> step_0 = dijkstra(dists);

  // inside commuter pass
  vector<int> step_1 = commuter_pass(step_0, d_house, d_school, school);

  // after leaving commuter pass
  vector<int> step_2 = dijkstra(step_1);

  cout << min({ step_0[book_v], step_1[book_v], step_2[book_v] }) << endl;
}

int32_t main() {
  solve();
  return 0;
}

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