Submission #1026169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026169		NguyenPhucThang	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	220 ms	78112 KiB

commuter_pass

#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<ll, pii>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 1e6 + 5;

vector<pll> g[N];
vi dag[N];
int n, m, s, t, U, V;
vector<ll> du, dv, ds, dt;
ll dpU[N], dpV[N];
int deg[N];

void dijkstra(int s, vector<ll> &d){
   d.resize(n + 1);
   priority_queue<pll, vector<pll>, greater<pll>> pq;
   
   forr(i, 1, n) d[i] = oo;
   d[s] = 0;
   pq.push({d[s], s});

   while (!pq.empty()){
      int u = pq.top().se;
      ll dis = pq.top().fi;
      pq.pop();
      if (dis > d[u]) continue;
      for(pll e : g[u]){
         ll v = e.fi, w = e.se;
         if (d[v] > dis + w){
            pq.push({d[v] = dis + w, v});
         }
      }
   }
}


   
int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin >> n >> m >> s >> t >> U >> V;
   while (m--){
      int x, y, w;
      cin >> x >> y >> w;
      g[x].pb({y, w});
      g[y].pb({x, w});
   }

   dijkstra(U, du);
   dijkstra(V, dv);
   dijkstra(s, ds);
   dijkstra(t, dt);

   forr(u, 1, n){
      for(pll e : g[u]){
         ll v = e.fi, w = e.se;
         if (ds[v] + w + dt[u] == dt[s]) {
            dag[v].pb(u), deg[u]++;
         }
      }
      dpU[u] = du[u];
      dpV[u] = dv[u];
   }

   ll ans = du[V];
   queue<int> q;
   q.push(s);
   dpU[s] = du[s], dpV[s] = dv[s];
   while (!q.empty()){
      int u = q.front();
      q.pop();
      ans = min({ans, dpU[u] + dv[u], dpV[u] + du[u]});
      for(int v : dag[u]){
         dpU[v] = min(dpU[u], dpU[v]);
         dpV[v] = min(dpV[u], dpV[v]);
         deg[v]--;
         if (!deg[v]) q.push(v);
      }
   }

   cout << ans;

   return 0;
}

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