제출 #434291

#제출 시각아이디문제언어결과실행 시간메모리
434291JovanK26Commuter Pass (JOI18_commuter_pass)C++14
16 / 100
656 ms27760 KiB
#include <bits/stdc++.h> using namespace std; long long n,m,s,t,u,v; vector< pair<long long,long long> > adj[100001]; long long ds[100001]; long long dt[100001]; long long du[100001]; long long dv[100001]; void dijkstra1(long long start=s) { for(long long i=0;i<n;i++) { ds[i]=1000000000000000000; } ds[start]=0; set< pair<long long,long long> > st; st.insert({ds[start],start}); while(!st.empty()) { long long cur=st.begin()->second; st.erase(st.begin()); for(auto p : adj[cur]) { long long node=p.first; long long len=p.second; if(ds[cur]+len<ds[node]) { st.erase({ds[node],node}); ds[node]=ds[cur]+len; st.insert({ds[node],node}); } } } } void dijkstra2(long long start=t) { for(long long i=0;i<n;i++) { dt[i]=1000000000000000000; } dt[start]=0; set< pair<long long,long long> > st; st.insert({dt[start],start}); while(!st.empty()) { long long cur=st.begin()->second; st.erase(st.begin()); for(auto p : adj[cur]) { long long node=p.first; long long len=p.second; if(dt[cur]+len<dt[node]) { st.erase({dt[node],node}); dt[node]=dt[cur]+len; st.insert({dt[node],node}); } } } } void dijkstra3(long long start=u) { for(long long i=0;i<n;i++) { du[i]=1000000000000000000; } du[start]=0; set< pair<long long,long long> > st; st.insert({du[start],start}); while(!st.empty()) { long long cur=st.begin()->second; st.erase(st.begin()); for(auto p : adj[cur]) { long long node=p.first; long long len=p.second; if(du[cur]+len<du[node]) { st.erase({du[node],node}); du[node]=du[cur]+len; st.insert({du[node],node}); } } } } void dijkstra4(long long start=v) { for(long long i=0;i<n;i++) { dv[i]=1000000000000000000; } dv[start]=0; set< pair<long long,long long> > st; st.insert({dv[start],start}); while(!st.empty()) { long long cur=st.begin()->second; st.erase(st.begin()); for(auto p : adj[cur]) { long long node=p.first; long long len=p.second; if(dv[cur]+len<dv[node]) { st.erase({dv[node],node}); dv[node]=dv[cur]+len; st.insert({dv[node],node}); } } } } long long f[100001]; long long rez=1000000000000000000; long long dfs(long long cur,bool is) { if(f[cur]==-1) { if(ds[cur]+dt[cur]==ds[t]) { f[cur]=dv[cur]; for(auto p : adj[cur]) { long long node=p.first; long long len=p.second; if(is && ds[cur]+len==ds[node]) { f[cur]=min(f[cur],dfs(node,is)); } else if(!is && dt[cur]+len==dt[node]) { f[cur]=min(f[cur],dfs(node,is)); } rez=min(rez,du[cur]+f[cur]); } } else { f[cur]=1000000000000000000; } } return f[cur]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; long long a,b,c; for(long long i=0;i<m;i++) { cin >> a >> b >> c; a--; b--; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } dijkstra1(); dijkstra2(); dijkstra3(); dijkstra4(); memset(f,-1,8*n); dfs(s,1); memset(f,-1,8*n); dfs(t,0); cout << rez; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...