Submission #1130048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130048		m_bezrutchka	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	338 ms	29888 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 LLINF = 2e18 + 10;
const int MAXN = 2e5 + 10;

int n, house, school;
vector<pii> adj[MAXN];
int dist_ini[2][MAXN];
bool mrk_ini[2][MAXN];
int dist[4][MAXN];
bool mrk[4][MAXN];

void dijkstra1(int t, int source) {
  for (int i = 1; i <= n; i++) {
    dist_ini[t][i] = LLINF;
  }
  dist_ini[t][source] = 0;
  priority_queue<pii> pq;
  pq.push({0, source});
  while (!pq.empty()) {
    auto [d, v] = pq.top();
    pq.pop();
    if (mrk_ini[t][v]) continue;
    mrk_ini[t][v] = true;
    for (auto [w, c]: adj[v]) {
      if (mrk_ini[t][w]) continue;
      if (dist_ini[t][w] > dist_ini[t][v] + c) {
        dist_ini[t][w] = dist_ini[t][v] + c;
        pq.push({-dist_ini[t][w], w});
      }
    }
  }
}

bool in_path(int v) {
  return dist_ini[0][v] + dist_ini[1][v] == dist_ini[0][school];
}

void dijkstra2(int source) {
  for (int i = 1; i <= n; i++) {
    dist[0][i] = dist[1][i] = dist[2][i] = dist[3][i] = LLINF;
  }
  dist[0][source] = 0;
  priority_queue<pip> pq;
  pq.push({0, {0, source}});
  while (!pq.empty()) {
    auto [d, p] = pq.top();
    auto [t, v] = p;
    pq.pop();
    if (mrk[t][v]) continue;
    mrk[t][v] = true;
    for (auto [w, c]: adj[v]) {
      bool both_in_path = in_path(v) && in_path(w);
      if (t == 0) {
        // before commuter pass
        if (dist[0][w] > dist[0][v] + c) {
          dist[0][w] = dist[0][v] + c;
          pq.push({-dist[0][w], {0, w}});
        }
        if (both_in_path) {
          if (dist_ini[0][w] == dist_ini[0][v] + c && dist[1][w] > dist[0][v]) {
            dist[1][w] = dist[0][v];
            pq.push({-dist[1][w], {1, w}});
          }
          if (dist_ini[1][w] == dist_ini[1][v] + c && dist[2][w] > dist[0][v]) {
            dist[2][w] = dist[0][v];
            pq.push({-dist[2][w], {2, w}});
          }
        }
      } else if (t == 1) {
        // inside commuter pass s -> t
        if (both_in_path) {
          if (dist_ini[0][w] == dist_ini[0][v] + c && dist[1][w] > dist[1][v]) {
            dist[1][w] = dist[1][v];
            pq.push({-dist[1][w], {1, w}});
          }
        }
        if (dist[3][w] > dist[1][v] + c) {
          dist[3][w] = dist[1][v] + c;
          pq.push({-dist[3][w], {3, w}});
        }
      } else if (t == 2) {
          // inside commuter pass t -> s
        if (both_in_path) {
          if (dist_ini[1][w] == dist_ini[1][v] + c && dist[2][w] > dist[2][v]) {
            dist[2][w] = dist[2][v];
            pq.push({-dist[2][w], {2, w}});
          }
        }
        if (dist[3][w] > dist[2][v] + c) {
          dist[3][w] = dist[2][v] + c;
          pq.push({-dist[3][w], {3, w}});
        }
      } else {
        // after commuter pass
        if (dist[3][w] > dist[3][v] + c) {
          dist[3][w] = dist[3][v] + c;
          pq.push({-dist[3][w], {3, w}});
        }
      }
    }
  }
}

void solve() {
  int m, u, v;
  cin >> n >> m >> house >> school >> u >> v;

  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }

  dijkstra1(0, house);
  dijkstra1(1, school);
  dijkstra2(u);

  cout << min({ dist[0][v], dist[1][v], dist[2][v], dist[3][v] }) << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

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