제출 #654617

#제출 시각아이디문제언어결과실행 시간메모리
654617leroycutCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
340 ms32520 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e18 + 3; const int N = 1e5 + 3; class cmt { public: bool operator() (pair<int, ll> a, pair<int, ll> b){ return a.second > b.second; } }; int s, t, v, u, n, m; vector<pair<int, ll>> g[N]; vector<int> dag1[N], dag2[N]; ll dpv[N], dpu[N]; vector<ll> ds, dv, du; bool us[N]; vector<ll> djikstra(int S){ vector<ll> d(N, INF); d[S] = 0; priority_queue<pair<int, ll>, vector<pair<int, ll>>, cmt> q; q.push({S, 0}); while(!q.empty()){ auto cur = q.top(); q.pop(); int node = cur.first; ll dist = cur.second; if(dist != d[node]) continue; for(auto i : g[node]){ if(dist + i.second < d[i.first]){ d[i.first] = dist + i.second; q.push({i.first, dist + i.second}); } } } return d; } void dfs(int S){ us[S] = true; for(auto i : g[S]){ if(us[i.first]) continue; if(ds[S] - i.second == ds[i.first]){ dag1[S].push_back(i.first); dag2[i.first].push_back(S); dfs(i.first); } } } ll ans = INF; void dfsp1(int S){ us[S] = true; dpu[S] = du[S]; dpv[S] = dv[S]; for(auto i : dag1[S]){ if(!us[i]){ dfsp1(i); } if(min(dpu[i], du[S]) + min(dpv[i], dv[S]) <= dpu[S] + dpv[S]){ dpu[S] = min(du[S], dpu[i]); dpv[S] = min(dv[S], dpv[i]); } } // cout << dpv[S] << " " << dpu[S] << " " << S << " !\n"; ans = min(ans, dpv[S] + dpu[S]); } void dfsp2(int S){ us[S] = true; dpu[S] = du[S]; dpv[S] = dv[S]; for(auto i : dag2[S]){ if(!us[i]){ dfsp2(i); } if(min(dpu[i], du[S]) + min(dpv[i], dv[S]) <= dpu[S] + dpv[S]){ dpu[S] = min(du[S], dpu[i]); dpv[S] = min(dv[S], dpv[i]); } } // cout << dpv[S] << " " << dpu[S] << " " << S << " !\n"; ans = min(ans, dpv[S] + dpu[S]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> v >> u; for(int i = 0; i < m; ++i){ int a, b; ll c; cin >> a >> b >> c; g[a].push_back({b, c}); g[b].push_back({a, c}); } ds = djikstra(s); du = djikstra(u); dv = djikstra(v); dfs(t); for(int i = 0; i < N; ++i){ dpu[i] = dpv[i] = INF; us[i] = false; } dfsp1(t); for(int i = 0; i < N; ++i){ dpu[i] = dpv[i] = INF; us[i] = false; } dfsp2(s); cout << min(ans, dv[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...