Submission #989671

#	Time	Username	Problem	Language	Result	Execution time	Memory
989671		kilkuwu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	176 ms	22504 KiB

commuter_pass

#include <bits/stdc++.h>
 
#define nl '\n'
 
template <typename B> 
inline bool ckmin(B& x, const B& y) {
  return y < x ? x = y, 1 : 0;
}
 
 
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int N, M, A, B, C, D;
  std::cin >> N >> M >> A >> B >> C >> D;
  --A, --B, --C, --D;
 
  std::vector<std::vector<std::pair<int, int>>> adj(N);
 
  for (int i = 0; i < M; i++) {
    int u, v, w;
    std::cin >> u >> v >> w;
    --u, --v;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
 
  auto dijkstra = [&](int st) -> std::vector<int64_t> {
    std::vector<int64_t> dp(N, 1e18);
    dp[st] = 0;
 
    std::priority_queue<std::pair<int64_t, int>> pq;
    pq.emplace(dp[st], st);
 
    while (pq.size()) {
      auto [d, u] = pq.top();
      pq.pop();
 
      d = -d;
 
      if (dp[u] < d) continue;
 
      for (auto [v, w] : adj[u]) {
        auto nd = d + w;
        if (nd < dp[v]) {
          dp[v] = nd;
          pq.emplace(-dp[v], v);
        }
      }
    }
 
    return dp;
  };
 
  auto dpC = dijkstra(C);
  auto dpD = dijkstra(D);
 
  auto dijkstra2 = [&](int st, std::vector<int64_t>& minC,
                       std::vector<int64_t>& minD) -> std::vector<int64_t> {
 
    std::vector<int64_t> dp(N, 1e18);
    dp[st] = 0;
 
    minC.assign(N, 1e18);
    minD.assign(N, 1e18);
 
    std::priority_queue<std::pair<int64_t, int>> pq;
    pq.emplace(dp[st], st);
 
    while (pq.size()) {
      auto [d, u] = pq.top();
      pq.pop();
 
      d = -d;
 
      if (dp[u] < d) continue;
 
      ckmin(minC[u], dpC[u]);
      ckmin(minD[u], dpD[u]);          
 
      for (auto [v, w] : adj[u]) {
        auto nd = d + w;
        if (nd == dp[v]) {
          ckmin(minC[v], minC[u]);
          ckmin(minD[v], minD[u]);
        } else if (nd < dp[v]) {
          minC[v] = minC[u];
          minD[v] = minD[u];
          dp[v] = nd;
          pq.emplace(-dp[v], v);
        }
      }
    }
 
    return dp;
  };
 
 
  std::vector<int64_t> minAC, minAD, minBC, minBD;
 
  auto dpA = dijkstra2(A, minAC, minAD);
  auto dpB = dijkstra2(B, minBC, minBD);
 
  int64_t ans = dpC[D];
  for (int i = 0; i < N; i++) {
    if (dpA[i] + dpB[i] == dpA[B]) {
      // this is an edge 
      ckmin(ans, minAC[i] + minBD[i]);
      ckmin(ans, minAD[i] + minBC[i]);
    }
  }
 
  std::cout << ans << nl;
}

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