제출 #848011

#제출 시각아이디문제언어결과실행 시간메모리
848011Derek0Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
434 ms31980 KiB
#include <bits/stdc++.h> using namespace std; #define overload4(a, b, c, d, name, ...) name #define rep1(i, n) for(ll i = 0; i < (n); ++i) #define rep2(i, a, b) for(ll i = (a); i < (b); ++i) #define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per1(i, n) for(ll i = (n) - 1; i >= 0; --i) #define per2(i, a, b) for(ll i = (b) - 1; i >= a; --i) #define per3(i, a, b, c) for(ll i = (b) - 1; i >= (a); i -= (c)) #define per(...) overload4(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define pb emplace_back #define lb(v,k) (ll) (lower_bound(all(v), (k)) - v.begin()) #define ub(v,k) (ll) (upper_bound(all(v), (k)) - v.begin()) #define all(a) a.begin(),a.end() #define fi first #define se second #define PQ(T) priority_queue<T> #define SPQ(T) priority_queue<T, vector<T>, greater<T>> typedef long long ll; typedef pair<ll,ll> P; using vi = vector<ll>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>; using vp = vector<P>; using vvp = vector<vp>; constexpr ll inf = (ll) 1e18; constexpr int _ = 100010; ll n, m, s, t, u, v; ll deg[_], mn[_][2]; vp g[_]; vi adj[_]; vi Dijkstra(ll s) { SPQ(P) h; h.emplace(0, s); vi dist(n, -1); while (!h.empty()) { auto [d, x] = h.top(); h.pop(); if (dist[x] != -1) continue; dist[x] = d; for (auto [y, w] : g[x]) { h.emplace(d + w, y); } } return dist; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; cin >> s >> t >> u >> v; --s; --t; --u; --v; rep(i, m) { ll a, b, c; cin >> a >> b >> c; --a; --b; g[a].pb(b, c); g[b].pb(a, c); } auto ds = Dijkstra(s); auto dt = Dijkstra(t); auto du = Dijkstra(u); auto dv = Dijkstra(v); rep(x, n) for (auto [y, w] : g[x]) { if (ds[x] + dt[y] + w == ds[t]) { adj[x].pb(y); deg[y]++; } } rep(i, n) mn[i][0] = mn[i][1] = inf; queue<ll> q; rep(i, n) if (deg[i] == 0) { q.push(i); mn[i][0] = du[i]; mn[i][1] = dv[i]; } ll ans = inf; while (!q.empty()) { ll x = q.front(); q.pop(); ans = min(ans, du[x] + dv[x]); for (ll y : adj[x]) { ll c1 = mn[x][0] + dv[y]; ll c2 = mn[x][1] + du[y]; ans = min({ans, c1, c2}); mn[y][0] = min({mn[y][0], mn[x][0], du[y]}); mn[y][1] = min({mn[y][1], mn[x][1], dv[y]}); if (--deg[y] == 0) q.push(y); } } cout << ans << '\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...