Submission #494704

#	Time	Username	Problem	Language	Result	Execution time	Memory
494704		keertan	Commuter Pass (JOI18_commuter_pass)	C++17	39 / 100	492 ms	35260 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int)(x.size())
const int N=1e5+5,N1=1e15,mod=1e9+7;
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
vector<int> adj1[N],adj2[N],adj3[N],disv(N,N1);
int memo[N];
int dp(int u){
  if (memo[u]!=-1){return memo[u];}
  int best=disv[u];
  for (int it:adj1[u]){
    best=min(best,dp(it));
  }
  return memo[u]=best;
}
int memo1[N];
int dpback(int u){
  if (memo1[u]!=-1){return memo1[u];}
  int best=disv[u];
  for (int it:adj2[u]){
    best=min(best,dpback(it));
  }
  return memo1[u]=best;
}
void solve(){
  int n,m,s,t,u,v;
  cin>>n>>m>>s>>t>>u>>v;
  using gh=pair<int,int>;
  vector<gh> adj[n+1];
  for (int i=1,x,y,w;i<=m;i++){
    cin>>x>>y>>w;
    adj[x].emplace_back(y,w);
    adj[y].emplace_back(x,w);
  }
  vector<int> disu(n+1,N1);
  min_heap<pair<int,int>> q;
  q.emplace(0,u);
  disu[u]=0;
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
    if (disu[nd]!=dis){continue;}
    for (const pair<int,int> &it:adj[nd]){
      if (disu[it.first]>dis+it.second){
        disu[it.first]=dis+it.second;
        q.emplace(disu[it.first],it.first);
      }
    }
  }
  disv[v]=0;
  q.emplace(0,v);
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
    if (disv[nd]!=dis){continue;}
    for (const pair<int,int> &it:adj[nd]){
      if (disv[it.first]>dis+it.second){
        disv[it.first]=dis+it.second;
        q.emplace(disv[it.first],it.first);
      }
    }
  }

  vector<int> curdis(n+1,N1);
  curdis[s]=0;
  q.emplace(0,s);
  vector<bool> curvis(n+1);
  while(!q.empty()){
    int nd,dis;
    tie(dis,nd)=q.top();
    q.pop();
   
    for (const pair<int,int> &it:adj[nd]){
      if (curdis[it.first]>dis+it.second){
        curdis[it.first]=dis+it.second;
        adj1[it.first].clear();
        adj1[it.first].emplace_back(nd);
        q.emplace(curdis[it.first],it.first);
      }
      else if (curdis[it.first]==dis+it.second){
        adj1[it.first].emplace_back(nd);
      }
    }
  }
 
  fill(all(curvis),false);
  queue<int> q1;
  q1.emplace(t);
  while(!q1.empty()){
    int nd=q1.front();
    q1.pop();
    if (curvis[nd]){continue;}
    curvis[nd]=1;
    for (const int &it:adj1[nd]){
      if (curvis[it]){continue;}
      adj2[it].emplace_back(nd);
      q1.emplace(it);
    }
  }
  
  
  
  
  
  memset(memo,-1,sizeof(memo));
  memset(memo1,-1,sizeof(memo1));

  int ans=disu[v];
  for (int i=1;i<=n;i++){
    if (!curvis[i]){continue;}
    ans=min(ans,disu[i]+min(dp(i),dpback(i)));
  }
  cout<<ans;
}
int32_t main(){
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  int tq=1;
  //cin>>tq;
  for (;tq;tq--){solve();}
} 

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