제출 #941805

#제출 시각아이디문제언어결과실행 시간메모리
941805carriewangCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
241 ms45296 KiB
#include <bits/stdc++.h> #define ll long long #define vi vector<int> #define pii pair<int,int> #define pll pair<ll,ll> #define sz(x) x.size() #define all(x) x.begin(),x.end() #define F first #define S second using namespace std; const int maxn=1000005; ll n,m,s,t,u,v,a,b,c; vector<pll> g[maxn]; vector<ll> dist(int x){ vector<ll> ret(n,1e18); priority_queue<pll,vector<pll>,greater<pll>> pq; pq.emplace(0,x); ret[x]=0; while(!pq.empty()){ auto [p,q]=pq.top(); pq.pop(); if(p>ret[q]) continue; for(auto [y,z]:g[q]){ if(p+z<ret[y]){ pq.emplace(p+z,y); ret[y]=p+z; } } } return ret; } int main(){ ios::sync_with_stdio(0),cin.tie(0); cin >> n >> m; cin >> s >> t >> u >> v; s--,t--,u--,v--; for(int i=0;i<m;i++){ cin >> a >> b >> c; a--,b--; g[a].emplace_back(b,c); g[b].emplace_back(a,c); } auto ds=dist(s),dt=dist(t),du=dist(u),dv=dist(v); vector<pll> ask; for(int i=0;i<n;i++){ if(ds[i]+dt[i]==ds[t]) ask.emplace_back(dt[i],i); } sort(all(ask)); ll ans=du[v]; vector<ll> um(n,1e18),vm(n,1e18); for(auto [_,x]:ask){ um[x]=du[x],vm[x]=dv[x]; for(auto [p,q]:g[x]){ if(dt[p]+q==dt[x]){ um[x]=min(um[x],um[p]); vm[x]=min(vm[x],vm[p]); } ans=min(ans,min(um[x]+dv[x],vm[x]+du[x])); } } 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...