제출 #676117

#제출 시각아이디문제언어결과실행 시간메모리
676117cristi_aCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
371 ms29892 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e15; const int nmax = 1e5; vector<vector<pair<ll, int>>> dx(nmax+5); vector<vector<int>> dag(nmax+5); int n, m, s, t, u, v; ll dist_s[nmax+5], dist_u[nmax+5], dist_v[nmax+5], ans, dpu[nmax+5], dpv[nmax+5]; bool viz[nmax+5]; void dij(int start, ll dist[]) { for(int i=1; i<=n; i++) { dist[i] = inf; dag[i].clear(); viz[i] = false; } dist[start] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.emplace(0, start); while(pq.empty() == false) { pair<ll, int> now = pq.top(); pq.pop(); if(viz[now.second]) continue; viz[now.second] = true; for(auto i : dx[now.second]) if(now.first + i.first < dist[i.second]) { dag[i.second] = {now.second}; dist[i.second] = now.first + i.first; pq.emplace(now.first + i.first, i.second); } else if(dist[i.second] == now.first + i.first) dag[i.second].emplace_back(now.second); } } void dfs(int node) { viz[node] = true; dpu[node] = min(dpu[node], dist_u[node]); dpv[node] = min(dpv[node], dist_v[node]); for(auto i : dag[node]) { if(!viz[i]) dfs(i); dpu[node] = min(dpu[node], dpu[i]); dpv[node] = min(dpv[node], dpv[i]); } ans = min(ans, dist_u[node] + dpv[node]); ans = min(ans, dist_v[node] + dpu[node]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> s >> t >> u >> v; for(int i=1; i<=m; i++) { int a, b; ll c; cin >> a >> b >> c; dx[a].emplace_back(c, b); dx[b].emplace_back(c, a); } dij(u, dist_u); dij(v, dist_v); dij(s, dist_s); for(int i=1; i<=n; i++) viz[i] = false; for(int i=1; i<=n; i++) { dpu[i] = inf; dpv[i] = inf; } ans = dist_v[u]; dfs(t); cout << ans; 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...