Submission #654597

#TimeUsernameProblemLanguageResultExecution timeMemory
654597leroycutCommuter Pass (JOI18_commuter_pass)C++17
15 / 100
2083 ms117460 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> dag[N]; ll dpv[N], dpu[N]; vector<ll> ds, dv, du; 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){ for(auto i : g[S]){ if(ds[i.first] < ds[S]){ if(ds[S] - i.second == ds[i.first]){ dag[S].push_back(i.first); dfs(i.first); } } } } ll ans = INF; void dfsp(int S){ dpu[S] = min(dpu[S], du[S]); dpv[S] = min(dpv[S], dv[S]); for(auto i : dag[S]){ dfsp(i); dpu[S] = min(dpu[i], dpu[S]); dpv[S] = min(dpv[i], dpv[S]); } ans = min(ans, dv[S] + dpu[S]); ans = min(ans, du[S] + dpv[S]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i = 0; i < N; ++i){ dpu[i] = dpv[i] = INF; } 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); dfsp(t); 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...