Submission #788730

#	Time	Username	Problem	Language	Result	Execution time	Memory
788730		tch1cherin	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	282 ms	15292 KiB

commuter_pass

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

const int MAX_N = 1e5 + 5;
vector<pair<int, int>> G[MAX_N];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, S, T, U, V;
  cin >> N >> M >> S >> T >> U >> V;
  S--, T--, U--, V--;
  for (int i = 0; i < M; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    A--, B--;
    G[A].push_back({B, C});
    G[B].push_back({A, C});
  }
  vector<int> order;
  vector<int64_t> dist(N);
  auto Dijkstra = [&](int start) {
    dist.assign(N, LLONG_MAX);
    order = vector<int>();
    priority_queue<pair<int64_t, int>> q;
    q.push({dist[start] = 0, start});
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      if (-d == dist[u]) {
        order.push_back(u);
        for (auto [v, w] : G[u])
          if (dist[u] + w < dist[v])
            q.push({-(dist[v] = w - d), v});
      }
    }
  };
  vector<int64_t> D[4];
  Dijkstra(U), D[0] = dist;
  Dijkstra(V), D[1] = dist;
  Dijkstra(T), D[3] = dist;
  Dijkstra(S), D[2] = dist;
  reverse(order.begin(), order.end());
  int64_t ans = LLONG_MAX;
  for (int u : order) {
    ans = min(ans, D[0][u] + D[1][u]);
    for (auto [v, w] : G[u]) {
      if (D[2][u] + w + D[3][v] == D[2][T]) {
        ans = min({ans, D[0][u] + D[1][v], D[0][v] + D[1][u]});
      }
    }
    for (auto [v, w] : G[u]) {
      if (D[2][u] + w + D[3][v] == D[2][T]) {
        D[0][u] = min(D[0][u], D[0][v]);
        D[1][u] = min(D[1][u], D[1][v]);
      }
    }
  }
  cout << min(D[0][V], ans) << "\n";
}

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