제출 #633549

#제출 시각아이디문제언어결과실행 시간메모리
633549colossal_pepeCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
664 ms28032 KiB
#include <iostream> #include <vector> #include <set> #include <tuple> using namespace std; using ll = long long; const ll INF = 1e15; int n, m, s, t, x, y; vector<vector<pair<int, ll>>> g; vector<ll> sssp(int start) { vector<ll> d(n, INF); set<pair<ll, int>> q; d[start] = 0; q.insert({0, start}); while (not q.empty()) { auto [dist, u] = *q.begin(); q.erase(q.begin()); for (auto [v, w] : g[u]) { if (d[u] + w < d[v]) { q.erase({d[v], v}); d[v] = d[u] + w; q.insert({d[v], v}); } } } return d; } ll solve(vector<ll> ds, vector<ll> dt, vector<ll> to_x, vector<ll> to_y) { ll ans = to_x[y]; vector<tuple<ll, ll, ll>> dp(n); for (int u = 0; u < n; u++) { auto &[dist, from_x, from_y] = dp[u]; dist = (u == s ? 0 : INF); from_x = to_x[u]; from_y = to_y[u]; } set<tuple<ll, ll, ll, int>> q; q.insert({0, to_x[s], to_y[s], s}); while (not q.empty()) { auto [dist, from_x, from_y, u] = *q.begin(); q.erase(q.begin()); if (ds[t] == ds[u] + dt[u]) ans = min(ans, min(from_x + to_y[u], from_y + to_x[u])); for (auto [v, w] : g[u]) { auto &[dist_v, from_x_v, from_y_v] = dp[v]; if (dist + w < dist_v) { q.erase({dist_v, from_x_v, from_y_v, v}); dist_v = dist + w; from_x_v = min(to_x[v], from_x); from_y_v = min(to_y[v], from_y); q.insert({dist_v, from_x_v, from_y_v, v}); } else if (dist + w == dist_v) { q.erase({dist_v, from_x_v, from_y_v, v}); from_x_v = min(from_x_v, from_x); from_y_v = min(from_y_v, from_y); q.insert({dist_v, from_x_v, from_y_v, v}); } } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> s >> t >> x >> y; s--, t--, x--, y--; g.resize(n); while (m--) { int a, b; ll w; cin >> a >> b >> w; a--, b--; g[a].push_back({b, w}); g[b].push_back({a, w}); } cout << solve(sssp(s), sssp(t), sssp(x), sssp(y)) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...