Submission #701629

#	Time	Username	Problem	Language	Result	Execution time	Memory
701629		EthanKim8683	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	475 ms	27712 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
using B=bool;
const I N=100000;
const Lli MAX=1e18;
vector<pair<I,I>>adjs[N];
vector<I>outs[N];
vector<I>incs[N];
Lli diss[N];
B viss[N];
priority_queue<pair<Lli,I>>ques;
void add1(I a,Lli d,I p){
  if(d>diss[a])return;
  if(d<diss[a])diss[a]=d,incs[a].clear(),ques.push({-d,a});
  if(d==diss[a])incs[a].push_back(p);
}
void add2(I a,Lli d){
  if(d>=diss[a])return;
  ques.push({-(diss[a]=d),a});
}
void dfs(I a){
  if(viss[a])return;
  viss[a]=1;
  for(auto b:incs[a]){
    outs[b].push_back(a);
    dfs(b);
  }
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n,m;cin>>n>>m;
  I s,t;cin>>s>>t,s--,t--;
  I u,v;cin>>u>>v,u--,v--;
  for(I i=0;i<m;i++){
    I a,b,c;cin>>a>>b>>c,a--,b--;
    adjs[a].push_back({b,c});
    adjs[b].push_back({a,c});
  }
  Lli res=MAX;
  for(I i=0;i<n;i++)incs[i].clear(),outs[i].clear();
  fill_n(diss,n,MAX),add2(s,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add1(b,d+c,a);
  }
  fill_n(viss,n,0),dfs(t);
  fill_n(diss,n,MAX),add2(u,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add2(b,d+c);
    for(auto b:outs[a])add2(b,d);
  }
  res=min(res,diss[v]);
  fill_n(diss,n,MAX),add2(v,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add2(b,d+c);
    for(auto b:outs[a])add2(b,d);
  }
  res=min(res,diss[u]);
  for(I i=0;i<n;i++)incs[i].clear(),outs[i].clear();
  fill_n(diss,n,MAX),add2(t,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add1(b,d+c,a);
  }
  fill_n(viss,n,0),dfs(s);
  fill_n(diss,n,MAX),add2(u,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add2(b,d+c);
    for(auto b:outs[a])add2(b,d);
  }
  res=min(res,diss[v]);
  fill_n(diss,n,MAX),add2(v,0);
  while(ques.size()){
    auto[d,a]=ques.top();ques.pop();
    if((d=-d)!=diss[a])continue;
    for(auto[b,c]:adjs[a])add2(b,d+c);
    for(auto b:outs[a])add2(b,d);
  }
  res=min(res,diss[u]);
  printf("%lli\n",res);
}

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