제출 #656303

#제출 시각아이디문제언어결과실행 시간메모리
656303Dec0DeddCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
317 ms24768 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; bool vis[N]; vector<pii> G[N]; vector<int> G2[N]; int n, m, ind[N]; ll ans=INF, dx[N], dy[N], mx[N], my[N]; void dijk(int s, ll *d) { 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 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}); } } } } void bfs() { queue<int> q; for (int i=1; i<=n; ++i) { if (ind[i] == 0) q.push(i); } while (!q.empty()) { int v=q.front(); q.pop(); mx[v]=min(mx[v], dx[v]), my[v]=min(my[v], dy[v]); ans=min({ans, dx[v]+my[v], mx[v]+dy[v]}); for (auto u : G2[v]) { --ind[u]; mx[u]=min(mx[u], mx[v]), my[u]=min(my[u], my[v]); if (ind[u] == 0) q.push(u); } } } 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 ds[n+1]={}, dt[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, ds), dijk(t, dt); ll k=ds[t]; for (int i=1; i<=n; ++i) { for (auto z : G[i]) { if (ds[i]+dt[z.second]+z.first == k) G2[i].push_back(z.second); if (ds[z.second]+dt[i]+z.first == k) G2[z.second].push_back(i); } } for (int i=1; i<=n; ++i) dx[i]=dy[i]=mx[i]=my[i]=INF; dijk(x, dx), dijk(y, dy); memset(vis, false, sizeof(vis)); for (int i=1; i<=n; ++i) { for (auto u : G2[i]) ++ind[u]; } bfs(); 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...