제출 #227913

#제출 시각아이디문제언어결과실행 시간메모리
227913syyCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
522 ms36000 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) ll n, m, s, t, u, v, a, b, c, ans = 1e17; ll dist[4][100005]; // s, t, u, v; vector<pi> adj[100005]; vector<ll> dag[100005], revdag[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)); } } } } ll dfs(ll x, bool d) { vis[x] = 1; ll best = dist[3][x]; if (best == -1) best = 1e17; for (auto it: (d ? dag[x] : revdag[x])) { if (vis[it]) continue; best = min(best, dfs(it, d)); } if (dist[2][x] == -1) return best; ans = min(ans, dist[2][x] + best); return best; } 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[0][a] == -1 or dist[0][b] == -1 or dist[1][a] == -1 or dist[1][b] == -1) continue; if (dist[1][a] + dist[0][b] + c == dist[0][t]) swap(a, b); if (dist[0][a] + dist[1][b] + c == dist[0][t]) { dag[a].pb(b); revdag[b].pb(a); } } dfs(s, 1); memset(vis, 0, sizeof vis); dfs(t, 0); cout << min(ans, dist[3][u]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...