Submission #494699

#	Time	Username	Problem	Language	Result	Execution time	Memory
494699		keertan	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	554 ms	36828 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=1e4+5,N1=1e15,mod=1e9+7;
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
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),disv(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> adj1[n+1];
  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);
      }
    }
  }
  vector<int> adj2[n+1];
  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);
    }
  }
  vector<int> adj3[n+1];
  for (int i=1;i<=n;i++){
    for (int it:adj2[i]){
      adj3[it].emplace_back(i);
    }
  }
 
  vector<int> indeg1(n+1),indeg2(n+1);
  for (int i=1;i<=n;i++){
    for (int it:adj2[i]){
      indeg1[it]++;
    }
  }
  for (int i=1;i<=n;i++){
    if (!indeg1[i]){
      
      q1.emplace(i);
    }
  }
  vector<int> forwarddp(n+1),backwardp(n+1);
  for (int i=1;i<=n;i++){
    forwarddp[i]=backwardp[i]=disv[i];
  }
  while(!q1.empty()){
    int nd=q1.front();
    q1.pop();
    for (const int  &it:adj2[nd]){
      indeg1[it]--;
      forwarddp[it]=min(forwarddp[it],forwarddp[nd]);
      if (indeg1[it]==0){q1.emplace(it);}
    }
  }
  for (int i=1;i<=n;i++){
    for (int it:adj3[i]){
      indeg2[it]++;
    }
  }
  for (int i=1;i<=n;i++){
    if (indeg2[i]==0){q1.emplace(i);}
  }
  while(!q1.empty()){
    int nd=q1.front();
    q1.pop();
    for (const int  &it:adj3[nd]){
      indeg2[it]--;
      backwardp[it]=min(backwardp[it],backwardp[nd]);
      if (indeg2[it]==0){q1.emplace(it);}
    }
  }
  
  assert(*max_element(all(indeg1))<=0);
    assert(1);

  int ans=disu[v];
  for (int i=1;i<=n;i++){
    if (!curvis[i]){continue;}
    ans=min(ans,disu[i]+min(forwarddp[i],backwardp[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: 0 / 24
• Subtask 4: 0 / 45