Submission #721586

#	Time	Username	Problem	Language	Result	Execution time	Memory
721586		Yell0	Commuter Pass (JOI18_commuter_pass)	C++17	55 / 100	310 ms	21468 KiB

commuter_pass

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
const int MN=1e5+2;
int N,M,S,T,U,V;
ll du[MN],dv[MN],dis[MN],uU[MN],uV[MN],mU[MN],mV[MN],vU[MN],vV[MN];
bool vis[MN];
vector<pii> gr[MN];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N>>M>>S>>T>>U>>V;
  for(int i=1;i<=M;++i) {
    int u,v,w;
    cin>>u>>v>>w;
    gr[u].push_back(pii(w,v));
    gr[v].push_back(pii(w,u));
  }

  fill(du+1,du+1+N,2e18);
  memset(vis,0,sizeof(vis));
  priority_queue<pii,vector<pii>,greater<pii>> pq;
  pq.push(pii(0,U));
  du[U]=0;
  while(!pq.empty()) {
    int u=pq.top().s;
    ll d=pq.top().f;
    pq.pop();
    if(vis[u]) continue;
    vis[u]=1;
    for(pii p:gr[u]) {
      int v=p.s;
      ll ed=p.f;
      if(!vis[v]&&d+ed<du[v]) {
        du[v]=d+ed;
        pq.push(pii(du[v],v));
      }
    }
  }

  fill(dv+1,dv+1+N,2e18);
  memset(vis,0,sizeof(vis));
  pq.push(pii(0,V));
  dv[V]=0;
  while(!pq.empty()) {
    int u=pq.top().s;
    ll d=pq.top().f;
    pq.pop();
    if(vis[u]) continue;
    vis[u]=1;
    for(pii p:gr[u]) {
      int v=p.s;
      ll ed=p.f;
      if(!vis[v]&&d+ed<dv[v]) {
        dv[v]=d+ed;
        pq.push(pii(dv[v],v));
      }
    }
  }

  // S->T
  fill(dis+1,dis+1+N,2e18);
  memset(vis,0,sizeof(vis));
  pq.push(pii(0,S));
  dis[S]=0;
  uU[S]=vU[S]=mU[S]=du[S];
  uV[S]=vV[S]=mV[S]=dv[S];
  while(!pq.empty()) {
    int x=pq.top().s;
    ll d=pq.top().f;
    pq.pop();
    if(vis[x]) continue;
    vis[x]=1;
    for(pii p:gr[x]) {
      int y=p.s;
      ll ed=p.f;
      if(!vis[y]) {
        if(d+ed<dis[y]) {
          dis[y]=d+ed;
          pq.push(pii(dis[y],y));
          uU[y]=min(uU[x],du[y]);
          uV[y]=min(uV[x],dv[y]);
          mU[y]=min(mU[x],du[y]);
          mV[y]=min(mV[x],dv[y]);
          vU[y]=min(vU[x],du[y]);
          vV[y]=min(vV[x],dv[y]);
          if(uU[y]+uV[y]<=mU[y]+mV[y]) {
            mU[y]=uU[y];
            mV[y]=uV[y];
          }
          if(vU[y]+vV[y]<=mU[y]+mV[y]) {
            mU[y]=vU[y];
            mV[y]=vV[y];
          }
        }
        if(d+ed==dis[y]) {
          if(uU[x]<uU[y]) {
            uU[y]=uU[x];
            uV[y]=uV[x];
          }
          if(vV[x]<vV[y]) {
            vU[y]=vU[x];
            vV[y]=vV[x];
          }
          if(mU[x]+mV[x]<mU[y]+mV[y]) {
            mU[y]=mU[x];
            mV[y]=mV[x];
          }
          mU[y]=min(mU[y],du[y]);
          mV[y]=min(mV[y],dv[y]);
          if(uU[y]+uV[y]<=mU[y]+mV[y]) {
            mU[y]=uU[y];
            mV[y]=uV[y];
          }
          if(vU[y]+vV[y]<=mU[y]+mV[y]) {
            mU[y]=vU[y];
            mV[y]=vV[y];
          }
        }
      }
    }
  }

  cout<<min(mU[T]+mV[T],du[V])<<'\n';
  return 0;
}

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