Submission #333527

#	Time	Username	Problem	Language	Result	Execution time	Memory
333527		a_player	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	537 ms	30432 KiB

commuter_pass

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

typedef long long ll;

const int nax=1e5+5;
vector<pair<int,ll> > grafo[nax];
vector<int> dag[nax];
ll dists[nax],distv[nax],distu[nax];
ll dpu[nax],dpv[nax];
bitset<nax> v;
priority_queue<pair<ll,int> > q;
void dfs(int n){
  if(v[n])return;
  v[n]=1;
  for(auto x:grafo[n])
    if(dists[n]+x.s==dists[x.f]){
      dag[x.f].push_back(n);
      dfs(x.f);
    }

}
void dijkstra(ll* d, int s, int n){
  for(int i=0;i<=n;i++)d[i]=LLONG_MAX;
  d[s]=0;
  q.emplace(0,s);
  while(!q.empty()){
    int co=q.top().s;
    q.pop();
    for(auto x:grafo[co])
      if(d[co]+x.s<d[x.f]){
        d[x.f]=d[co]+x.s;
        q.emplace(-d[x.f],x.f);
      }
  }
}
ll ricu(int n, int s){
  if(n==s)return distu[s];
  if(dpu[n]!=-1)return dpu[n];
  dpu[n]=distu[n];
  for(int x:dag[n]){
    dpu[n]=min(dpu[n],ricu(x,s));
  }
  return dpu[n];
}
ll ricv(int n, int s){
  if(n==s)return distv[s];
  if(dpv[n]!=-1)return dpv[n];
  dpv[n]=distv[n];
  for(int x:dag[n]){
    dpv[n]=min(dpv[n],ricv(x,s));
  }
  return dpv[n];
}
int main(){
  int n,m,s,t,u,v;
  cin>>n>>m>>s>>t>>u>>v;
  t--,u--,v--,s--;
  for(int i=0;i<m;i++){
    ll a,b,c;
    cin>>a>>b>>c;
    a--,b--;
    grafo[a].emplace_back(b,c);
    grafo[b].emplace_back(a,c);
  }
  dijkstra(dists,s,n);
  dijkstra(distv,v,n);
  dijkstra(distu,u,n);
  dfs(s);
  memset(dpv,-1,sizeof(dpv));
  memset(dpu,-1,sizeof(dpu));
  ricu(t,s);
  ricv(t,s);
  ll sol=LLONG_MAX;
  for(int i=0;i<n;i++)if(dpv[i]!=-1)sol=min(sol,dpu[i]+dpv[i]);
  cout<<sol<<endl;

}

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