Submission #1128354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128354		m_bezrutchka	Commuter Pass (JOI18_commuter_pass)	C++20	55 / 100	2099 ms	95500 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;
}

void print_map(map<pii, int> &mp) {
  for (auto [k, val]: mp) {
    cout << k.first << " " << k.second << " -> " << val << endl;
  }
}

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++) {
    if (dh[i] + ds[i] == dh[school]) {
      dist[{i, 0}] = start_distances[i];
      in_path[i] = true;
    } else {
      dist[{i, 0}] = LLINF;
    }
    pq.push({{-dist[{i, 0}], -dist[{i, 0}]}, {i, 0}});
  }
  for (int v = 1; v <= n; v++) {
    for (auto [w, c]: adj[v]) {
      dist[{w, v}] = LLINF;
      pq.push({{-dist[{w, v}], -dist[{w, v}]}, {v, w}});      
    }
  }

  // print_map(dist);

  while (!pq.empty()) {
    int d = -pq.top().first.first;
    int cp = -pq.top().first.second;
    int v = pq.top().second.first;
    int p = pq.top().second.second;
    pq.pop();
    if (d == LLINF || mrk.count({v, p})) continue;
    mrk.insert({v, p});
    // cout << "processing " << v << " " << p << endl;
    
    for (auto [w, c]: adj[v]) {
      // printf("looking at %lld -> %lld -> %lld\n", p, v, w);
      if ((p == 0 && in_path[w]) || dh[p] + cp + c + ds[w] == dh[school] || ds[p] + cp + c + dh[w] == dh[school]) {
        if (!mrk.count({w, v}) && dist[{w, v}] > dist[{v, p}]) {
          dist[{w, v}] = dist[{v, p}];
          pq.push({{-dist[{w, v}], -c}, {w, v}});
          // printf("updated!\n");
        } else {
          // printf("not updated\n");
        }
      }
    }
    // print_map(dist);
  }

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

void print_dists(vector<int> &v) {
  for (int i = 1; i <= n; i++) {
    cout << i << " -> " << v[i] << endl;
  }
}

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);
  // cout << "after dijkstra from house:" << endl;
  // print_dists(d_house);

  dists[house] = LLINF;
  dists[school] = 0;
  vector<int> d_school = dijkstra(dists);
  // cout << "after dijkstra from school:" << endl;
  // print_dists(d_school);

  dists[school] = LLINF;
  dists[book_u] = 0;
  vector<int> step_0 = dijkstra(dists);
  // cout << "after dijkstra from book u:" << endl;
  // print_dists(step_0);

  // inside commuter pass
  vector<int> step_1 = commuter_pass(step_0, d_house, d_school, school);
  // cout << "after commuter pass:" << endl;
  // print_dists(step_1);

  // after leaving commuter pass
  vector<int> step_2 = dijkstra(step_1);
  // cout << "after post-commuter pass dijkstra:" << endl;
  // print_dists(step_2);

  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