Submission #1125148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125148		barkolorious	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	581 ms	32712 KiB

commuter_pass

// barkolorious - 08 December 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define all(v) (v).begin(), (v).end()
#define int long long
#define pb  push_back
#define sz  size
#define fr  first
#define sc  second
#define __  << " " << 

const int N = 2e5 + 5;
int distU[N], distV[N], distS[N], dpU[N], dpV[N];
vector<pair<int, int>> adj[N];
int vis[N], ans;

void dijsktra1 (int root, int dist[]) {
  fill(vis, vis + N, false);

  priority_queue<pair<int, int>> pq;
  pq.push({0, root});
  while (!pq.empty()) {
    int d = pq.top().fr, u = pq.top().sc;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    dist[u] = -d;
    // cout << u __ -d << endl;
    for (auto edge : adj[u]) {
      int v = edge.fr, w = edge.sc;
      pq.push({d - w, v});
    }
  }
}

void dijsktra2 (int start, int end) {
  fill(vis, vis + N, false);
  fill(dpU, dpU + N, 1e15);
  fill(dpV, dpV + N, 1e15);

  priority_queue<pair<int, pair<int, int>>> pq;
  pq.push({0, {start, 0}});
  dpU[0] = dpV[0] = 1e15;
  while (!pq.empty()) {
    int d, u, par;
    pair<int, int> p;
    tie(d, p) = pq.top();
    tie(u, par) = p;
    pq.pop();
    if (!vis[u]) {
      vis[u] = true;
      distS[u] = -d;
      dpU[u] = min(distU[u], dpU[par]);
      dpV[u] = min(distV[u], dpV[par]);
      for (auto edge : adj[u]) {
        int v = edge.fr, w = edge.sc;
        pq.push({d - w, {v, u}});
      }
    } else if (-d == distS[u]) {
      if (min(distU[u], dpU[par]) + min(distV[u], dpV[par]) <= dpU[u] + dpV[u]) {
        dpU[u] = min(distU[u], dpU[par]);
        dpV[u] = min(distV[u], dpV[par]);
      }
    }
  }

  ans = min(ans, dpU[end] + dpV[end]);
}

void solve () {
  int n, m; cin >> n >> m;
  int S, T, U, V; cin >> S >> T >> U >> V;
  for (int i = 0; i < m; i++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].pb({v, w});
    adj[v].pb({u, w});
  }

  dijsktra1(U, distU);
  dijsktra1(V, distV);

  ans = distU[V];

  dijsktra2(S, T);
  dijsktra2(T, S);

  cout << ans << endl;
}

/*
-- Sample 1 --
Input:
6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1
Output:
2

-- Sample 2 --
Input:
6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
Output:
3000000000

-- Sample 3 --
Input:
8 8
5 7
6 8
1 2 2
2 3 3
3 4 4
1 4 1
1 5 5
2 6 6
3 7 7
4 8 8
Output:
15

-- Sample 4 --
Input:
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10
Output:
0

-- Sample 5 --
Input:
10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16
Output:
19
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\JOI18\JOI18_commuter_pass.cpp" -o _run
*/

int32_t main () {
  #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #ifdef LOCAL
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #endif

  solve();

  #ifdef LOCAL
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #endif

  return 0;
}

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