Submission #922099

#	Time	Username	Problem	Language	Result	Execution time	Memory
922099		Aiperiii	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	472 ms	28420 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int> >g[N];
int ds[N],dv[N],du[N],vis[N],dpU[N],dpV[N];
int res=0;
void dfs(int v){
   if(vis[v])return;
   vis[v]=1;
   dpU[v]=du[v];dpV[v]=dv[v];
   for(auto to : g[v]){
      if(ds[v]==ds[to.ff]+to.ss){
         dfs(to.ff);
         dpU[v]=min(dpU[v],dpU[to.ff]);
         dpV[v]=min(dpV[v],dpV[to.ff]);
      }
   }
   res=min(res,dpU[v]+dv[v]);
   res=min(res,dpV[v]+du[v]);
}
signed main(){
   int n,m,s,t,u,w;
   cin>>n>>m>>s>>t>>u>>w;
   for(int i=0;i<m;i++){
      int a,b,c;
      cin>>a>>b>>c;
      g[a].pb({b,c});
      g[b].pb({a,c});
   }
   set <pair <int,int> > st;
   for(int i=1;i<=n;i++){
      ds[i]=1e18;du[i]=1e18;dv[i]=1e18;
   }
   ds[s]=0;
   st.insert({0,s});
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(auto to : g[v]){
         if(ds[to.ff]>ds[v]+to.ss){
            st.erase({ds[to.ff],to.ff});
            ds[to.ff]=ds[v]+to.ss;
            st.insert({ds[to.ff],to.ff});
         }
      }
   }
   du[u]=0;
   st.insert({0,u});
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(auto to : g[v]){
         if(du[to.ff]>du[v]+to.ss){
            st.erase({du[to.ff],to.ff});
            du[to.ff]=du[v]+to.ss;
            st.insert({du[to.ff],to.ff});
         }
      }
   }
   dv[w]=0;
   st.insert({0,w});
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(auto to : g[v]){
         if(dv[to.ff]>dv[v]+to.ss){
            st.erase({dv[to.ff],to.ff});
            dv[to.ff]=dv[v]+to.ss;
            st.insert({dv[to.ff],to.ff});
         }
      }
   }
   res=du[w];
   dfs(t);
   cout<<res<<"\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45