제출 #1032599

#제출 시각아이디문제언어결과실행 시간메모리
1032599MinhBossCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
203 ms30616 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define endl '\n' #define int long long const ll MOD = 1e9+7; void add(ll &x, const ll y){ x+= y; if(x>=MOD) x-= MOD; } bool maximize(ll &x, const ll y){ if(x < y){ x = y; return true; } return false; } bool minimize(ll &x, const ll y){ if(x > y){ x = y; return true; } return false; } const ll MAX = 2e5+10, INF = 1e18; ll n,m,k; ll du[MAX], dv[MAX], ds[MAX], dpU[MAX], dpV[MAX]; bool vis[MAX]; vector<pair<ll,ll>>adj[MAX]; ll res=INF; void dijkstra1(ll sta, ll *dist){ priority_queue<pair<ll,ll>>q; dist[sta] = 0; q.push({0, sta}); memset(vis, false, sizeof vis); while(!q.empty()){ ll u = q.top().se; q.pop(); if(vis[u]) continue; vis[u] = true; for(auto p : adj[u]){ if(dist[p.fi] > dist[u] + p.se){ dist[p.fi] = dist[u] + p.se; q.push({-dist[p.fi], p.fi}); } } } } void dijkstra2(ll sta, ll fin){ memset(vis, false, sizeof vis); memset(dpU, 0x3f, sizeof dpU); memset(dpV, 0x3f, sizeof dpV); memset(ds, 0x3f, sizeof ds); priority_queue<pair<ll,ll>>q; ds[sta] = 0; dpU[sta] = du[sta]; dpV[sta] = dv[sta]; q.push({0,sta}); while(!q.empty()){ ll u= q.top().se; q.pop(); if(vis[u]) continue; vis[u] = true; for(auto p : adj[u]){ if(ds[p.fi] > ds[u] + p.se){ ds[p.fi] = ds[u] + p.se; dpU[p.fi] = min(dpU[u], du[p.fi]); dpV[p.fi] = min(dpV[u], dv[p.fi]); q.push({-ds[p.fi], p.fi}); } else if(ds[p.fi] == ds[u] + p.se && dpU[p.fi] + dpV[p.fi] > min(dpU[u], du[p.fi]) + min(dpV[u], dv[p.fi])){ dpU[p.fi] = min(dpU[u], du[p.fi]); dpV[p.fi] = min(dpV[u], dv[p.fi]); } } } minimize(res, dpU[fin] + dpV[fin]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("shortcut.in","r",stdin); // freopen("shortcut.out","w",stdout); int s,t,u,v; cin>>n>>m>>s>>t>>u>>v; for(int i =1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; adj[u].pb({v,w}); adj[v].pb({u,w}); } memset(du,0x3f, sizeof du); memset(dv, 0x3f, sizeof dv); dijkstra1(u,du); dijkstra1(v,dv); res = du[v]; dijkstra2(s,t); // for(int i=1;i<=n;i++) cout<<ds[i]<<" "; // cout<<endl; cout<<res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...