제출 #979163

#제출 시각아이디문제언어결과실행 시간메모리
979163kilkuwuCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
245 ms22704 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...