Submission #1026172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026172		NguyenPhucThang	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	206 ms	74896 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[u] + w + dt[v] == ds[t]) {
            dag[u].pb(v), deg[v]++;
         }
      }
      dpU[u] = du[u], dpV[u] = dv[u];
   }

   ll ans = du[V];
   queue<int> q;
   dpU[s] = du[s];
   dpV[s] = dv[s];
   q.push(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