제출 #227941

#제출 시각아이디문제언어결과실행 시간메모리
227941syyCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
528 ms34080 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++) #define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--) typedef pair<ll, ll> pi; typedef pair<pi, ll> pii; #define f first #define s second #define pb push_back #define all(v) v.begin(), v.end() #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) const ll INF = 1e16; ll n, m, s, t, u, v, a, b, c; ll dp[100005], ex[100005], en[100005], dist[4][100005]; // s, t, u, v vector<pi> adj[100005]; vector<ll> dag[100005]; vector<pii> edges; bool vis[100005]; void dijkstra(ll source, ll id) { priority_queue<pi, vector<pi>, greater<pi> > pq; dist[id][source] = 0; pq.push(pi(0LL, source)); while (!pq.empty()) { auto [d, x] = pq.top(); pq.pop(); if (d != dist[id][x]) continue; for (auto it:adj[x]) { if (dist[id][it.f] == -1 or dist[id][it.f] > dist[id][x] + it.s) { dist[id][it.f] = dist[id][x] + it.s; pq.push(pi(dist[id][it.f], it.f)); } } } } void dfs(ll x) { if (vis[x]) return; vis[x] = 1; ex[x] = dist[3][x], en[x] = dist[2][x]; for (auto it:dag[x]) { dfs(it); if (ex[it] != -1) ex[x] = min(ex[x], ex[it]); if (en[it] != -1) en[x] = min(en[x], en[it]); } } ll dpf(ll x) { if (dp[x] != -1) return dp[x]; dp[x] = INF; ll mex = INF, men = INF; if (ex[x] != -1) mex = ex[x]; if (en[x] != -1) men = en[x]; for (auto it:dag[x]) dp[x] = min(dp[x], dpf(it)); if (dist[2][x] != -1) dp[x] = min(dp[x], dist[2][x] + mex); if (dist[3][x] != -1) dp[x] = min(dp[x], dist[3][x] + men); if (dist[2][x] != -1 and dist[3][x] != -1) dp[x] = min(dp[x], dist[2][x] + dist[3][x]); return dp[x]; } int main() { fastio; cin >> n >> m >> s >> t >> u >> v; FOR(i, 1, m) { cin >> a >> b >> c; adj[a].pb(pi(b, c)); adj[b].pb(pi(a, c)); edges.pb(pii(pi(a, b), c)); } memset(dist, -1, sizeof dist); dijkstra(s, 0); dijkstra(t, 1); dijkstra(u, 2); dijkstra(v, 3); for (auto it:edges) { a = it.f.f, b = it.f.s, c = it.s; if (dist[1][a] != -1 and dist[0][b] != -1 and dist[1][a] + dist[0][b] + c == dist[0][t]) dag[b].pb(a); else if (dist[0][a] != -1 and dist[1][b] != -1 and dist[0][a] + dist[1][b] + c == dist[0][t]) dag[a].pb(b); } dfs(s); memset(dp, -1, sizeof dp); ll ans = dpf(s); if (dist[3][u] != -1) ans = min(ans, dist[3][u]); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...