Submission #721560

#	Time	Username	Problem	Language	Result	Execution time	Memory
721560		Yell0	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	294 ms	22248 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],cu[MN],cv[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,1e18);
  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,1e18);
  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,1e18);
  fill(cu+1,cu+1+N,1e18);
  fill(cv+1,cv+1+N,1e18);
  memset(vis,0,sizeof(vis));
  pq.push(pii(0,S));
  dis[S]=0;
  cu[S]=du[S];
  cv[S]=dv[S];
  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]) {
        if(d+ed<dis[v]) {
          dis[v]=d+ed;
          cu[v]=min(cu[u],du[v]);
          cv[v]=min(cv[u],dv[v]);
          pq.push(pii(dis[v],v));
        }
        if(d+ed==dis[v]) {
          cu[v]=min({cu[u],cu[v],du[v]});
          cv[v]=min({cv[u],cv[v],dv[v]});
        }
      }
    }
  }

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

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