제출 #1086670

#제출 시각아이디문제언어결과실행 시간메모리
1086670khoile25108Commuter Pass (JOI18_commuter_pass)C++14
100 / 100
297 ms31612 KiB
#include <bits/stdc++.h> using namespace std; #define faster ios_base::sync_with_stdio(0); cin.tie(0); #define FOR(i,a,b) for(int i = a; i <= b; i++) #define FOD(i,a,b) for(int i = a; i >= b; i--) #define int long long #define fi first #define se second #define pb push_back #define ll long long #define ull unsigned long long #define lcm(a,b) (a*b)/__gcd(a,b) #define ii pair<int,int> #define iii pair<int,pair<int,int>> #define iv pair<pair<int,int>,pair<int,int>> const int inf = 1e9; const ll INF = 1e18; const int mod = 1e9 + 7; const int N = 1e5 + 105; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const int dxx[] = {-1,-1,0,1,1,1,0,-1}; const int dyy[] = {0,1,1,1,0,-1,-1,-1}; int n, m, S, T, U, V, ans; vector<ii> g[N]; int du[N], dv[N], dp[N][2], ds[N]; void dijk1(int beg, int d[]) { priority_queue<ii,vector<ii>,greater<ii>> pq; FOR(i,1,n) d[i] = INF; d[beg] = 0; pq.push({0,beg}); while(!pq.empty()) { int u = pq.top().se; int cost = pq.top().fi; pq.pop(); if(cost > d[u]) continue; for(ii H : g[u]) { int v = H.fi; int l = H.se; if(d[v] > d[u] + l) { d[v] = d[u] + l; pq.push({d[v],v}); } } } } void dijk2(int beg, int des) { priority_queue<iii,vector<iii>,greater<iii>> pq; pq.push({0,{0,beg}}); FOR(i,0,n) { dp[i][0] = INF; dp[i][1] = INF; ds[i] = INF; } while(!pq.empty()) { int u = pq.top().se.se; int par = pq.top().se.fi; int cost = pq.top().fi; pq.pop(); if(ds[u] == INF) { ds[u] = cost; dp[u][0] = min(dp[par][0], du[u]); dp[u][1] = min(dp[par][1], dv[u]); for(ii H : g[u]) pq.push({cost + H.se, {u, H.fi}}); } else if(ds[u] == cost) { if(min(dp[par][0], du[u]) + min(dp[par][1], dv[u]) <= dp[u][0] + dp[u][1]) { dp[u][0] = min(dp[par][0], du[u]); dp[u][1] = min(dp[par][1], dv[u]); } } } ans = min(ans, dp[des][0] + dp[des][1]); } void solve() { dijk1(U,du); dijk1(V,dv); ans = du[V]; dijk2(S,T); dijk2(T,S); cout << ans; } void input() { //freopen("TEST.INP", "r", stdin); //freopen("TEST.OUT", "w", stdout); cin >> n >> m >> S >> T >> U >> V; FOR(i,1,m) { int u, v, w; cin >> u >> v >> w; g[u].pb({v,w}); g[v].pb({u,w}); } } signed main() { faster input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...