Submission #979163

#	Time	Username	Problem	Language	Result	Execution time	Memory
979163		kilkuwu	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	245 ms	22704 KiB

commuter_pass

#include <bits/stdc++.h>

#define nl '\n'

template <typename T> 
inline bool ckmin(T& x, const T& y) {
  return y < x ? x = y, 1 : 0;
}


signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int N, M, S, T, U, V;
  std::cin >> N >> M >> S >> T >> U >> V;
  --S, --T, --U, --V;

  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 dpU = dijkstra(U);
  auto dpV = dijkstra(V);

  auto dijkstra2 = [&](int st, std::vector<int64_t>& minU,
                       std::vector<int64_t>& minV) -> std::vector<int64_t> {

    std::vector<int64_t> dp(N, 1e18);
    dp[st] = 0;

    minU.assign(N, 1e18);
    minV.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(minU[u], dpU[u]);
      ckmin(minV[u], dpV[u]);          

      for (auto [v, w] : adj[u]) {
        auto nd = d + w;
        if (nd == dp[v]) {
          ckmin(minU[v], minU[u]);
          ckmin(minV[v], minV[u]);
        } else if (nd < dp[v]) {
          minU[v] = minU[u];
          minV[v] = minV[u];
          dp[v] = nd;
          pq.emplace(-dp[v], v);
        }
      }
    }

    return dp;
  };


  std::vector<int64_t> minSU, minSV, minTU, minTV;

  auto dpS = dijkstra2(S, minSU, minSV);
  auto dpT = dijkstra2(T, minTU, minTV);

  int64_t ans = dpU[V];
  for (int i = 0; i < N; i++) {
    if (dpS[i] + dpT[i] == dpS[T]) {
      // this is an edge 
      ckmin(ans, minSU[i] + minTV[i]);
      ckmin(ans, minSV[i] + minTU[i]);
    }
  }

  std::cout << ans << nl;
}

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