Submission #1175084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175084		duonggsimp	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	196 ms	41236 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ii,ll> iii;
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define MOD 1000000007
const int N = 2e6;

ll n,m;
ll s,t,u,v;
ll ds[1000005];
ll dt[1000005];
ll du[1000005];
ll dv[1000005];
vector <ii> a[1000005];
priority_queue <ii,vector<ii>,greater<ii>> q;

void ditcha(ll d[],ll x){

  for (long i=1; i<=n; i++) d[i] = 1e15;
  d[x] = 0;
  q.push({0,x});

  while (!q.empty()){

    ii t = q.top(); q.pop();
    if (t.fi != d[t.se]) continue;

    for (ii i : a[t.se]){
      if (d[i.fi] > d[t.se] + i.se){
        d[i.fi] = d[t.se] + i.se;
        q.push({d[i.fi],i.fi});
      }
    }
  }
}

signed main(){

  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);

  cin >> n >> m;
  cin >> s >> t;
  cin >> u >> v;

  for (long i=1; i<=m; i++){
    ll u,v,w; cin >> u >> v >> w;
    a[u].pb({v,w});
    a[v].pb({u,w});
  }

  ditcha(ds,s);
  ditcha(dt,t);

  for (long i=1; i<=n; i++){
    for (ii it : a[i]){
      if (ds[i] + dt[it.fi] + it.se == ds[t]) a[i].pb({it.fi,0});
    }
  }

  ditcha(du,u);
  ditcha(dv,v);

  cout << min(du[v],dv[u]);
  return 0;
}

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