Submission #656298

#TimeUsernameProblemLanguageResultExecution timeMemory
656298Dec0DeddCommuter Pass (JOI18_commuter_pass)C++14
0 / 100
2091 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, int> const int N = 1e5+1; const ll INF = 1e18; vector<pii> G[N]; vector<int> G2[N]; int n, m; vector<int> par[N]; ll ans=INF, dx[N], dy[N]; void dijk(int s, ll *d, bool bl) { for (int i=1; i<=n; ++i) d[i]=INF; d[s]=0; priority_queue<pii, vector<pii>, greater<pii>> pq; pq.push({0, s}); while (!pq.empty()) { ll x=pq.top().first, v=pq.top().second; pq.pop(); if (x > d[v]) continue; for (auto u : par[v]) { G2[v].push_back(u); } for (auto z : G[v]) { ll w=z.first, u=z.second; if (d[u] > d[v]+w) { d[u]=d[v]+w; pq.push({d[u], u}); if (bl) par[u].clear(), par[u].push_back(v); } else if (d[u] == d[v]+w && bl) par[u].push_back(v); } } } void gen(int v) { for (auto u : par[v]) { G2[v].push_back(u); gen(u); } } void dfs(int v, ll mx, ll my) { mx=min(mx, dx[v]), my=min(my, dy[v]); ans=min(ans, mx+my); for (auto u : G2[v]) dfs(u, mx, my); } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; int s, t; cin>>s>>t; int x, y; cin>>x>>y; ll d[n+1]={}; for (int i=1; i<=m; ++i) { int a, b, c; cin>>a>>b>>c; G[a].push_back({c, b}); G[b].push_back({c, a}); } dijk(s, d, true); gen(t); for (int i=1; i<=n; ++i) par[i].clear(); for (int i=1; i<=n; ++i) dx[i]=dy[i]=INF; dijk(x, dx, false), dijk(y, dy, false); dfs(t, INF, INF); ans=min(ans, dx[y]); cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...