제출 #670373

#제출 시각아이디문제언어결과실행 시간메모리
670373finn__Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
408 ms24348 KiB
#include <bits/stdc++.h> using namespace std; size_t n, m; vector<vector<pair<unsigned, int64_t>>> g; void dijkstra(unsigned s, vector<int64_t> &dis, vector<vector<unsigned>> *pre = 0) { priority_queue<pair<int64_t, unsigned>, vector<pair<int64_t, unsigned>>, greater<pair<int64_t, unsigned>>> q; q.push({0, s}); dis[s] = 0; while (!q.empty()) { auto const [z, u] = q.top(); q.pop(); if (dis[u] != z) continue; for (auto const &[v, w] : g[u]) { if (z + w < dis[v]) { dis[v] = z + w; q.push({z + w, v}); if (pre) { (*pre)[v].clear(); (*pre)[v].push_back(u); } } else if (z + w == dis[v] && pre) { (*pre)[v].push_back(u); } } } } int64_t min_cost( unsigned s, unsigned t, unsigned x, unsigned y, vector<int64_t> const &s_dis, vector<vector<unsigned>> const &s_pre, vector<int64_t> const &x_dis, vector<int64_t> const &y_dis) { vector<int64_t> min_y_dis(n); for (unsigned u = 0; u < n; u++) min_y_dis[u] = y_dis[u]; vector<bool> vis(n, 0); vis[t] = 1; int64_t min_total = INT64_MAX; priority_queue<pair<int64_t, unsigned>, vector<pair<int64_t, unsigned>>, greater<pair<int64_t, unsigned>>> q; q.push({min_y_dis[t], t}); while (!q.empty()) { auto const [z, u] = q.top(); q.pop(); if (z != min_y_dis[u]) continue; min_total = min(min_total, min_y_dis[u] + x_dis[u]); for (unsigned v : s_pre[u]) { if (min_y_dis[u] < min_y_dis[v]) { min_y_dis[v] = min_y_dis[u]; q.push({min_y_dis[v], v}); } else if (!vis[v]) { q.push({min_y_dis[v], v}); vis[v] = 1; } } } return min_total; } int main() { cin >> n >> m; unsigned s, t, x, y; cin >> s >> t >> x >> y; s--, t--, x--, y--; g = vector<vector<pair<unsigned, int64_t>>>(n); for (size_t i = 0; i < m; i++) { unsigned u, v; int64_t w; cin >> u >> v >> w; g[u - 1].push_back({v - 1, w}); g[v - 1].push_back({u - 1, w}); } vector<int64_t> x_dis(n, INT64_MAX), y_dis(n, INT64_MAX); dijkstra(x, x_dis); dijkstra(y, y_dis); vector<int64_t> s_dis(n, INT64_MAX); vector<vector<unsigned>> s_pre(n); dijkstra(s, s_dis, &s_pre); cout << min(x_dis[y], min(min_cost(s, t, x, y, s_dis, s_pre, x_dis, y_dis), min_cost(s, t, y, x, s_dis, s_pre, y_dis, x_dis))) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...