Submission #481597

#	Time	Username	Problem	Language	Result	Execution time	Memory
481597		Soumya1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	265 ms	22540 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
vector<pair<int, int>> ad[mxN];
void dijkstra(int u, vector<long long> &d, int n) {
  priority_queue<pair<long long, int>> pq;
  pq.push({0, u});
  d[u] = 0;
  vector<bool> vis(n + 1);
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto [v, w] : ad[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.push({-d[v], v});
      }
    }
  }
}
void testCase() {
  int n, m, s, t, u, v;
  cin >> n >> m >> s >> t >> u >> v;
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  vector<long long> du(n + 1, 1e18), dv(n + 1, 1e18);
  dijkstra(u, du, n);
  dijkstra(v, dv, n);
  vector<long long> d(n + 1, 1e18);
  vector<bool> vis(n + 1);
  vector<long long> min_du(n + 1, 1e18), min_dv(n + 1, 1e18);
  priority_queue<pair<long long, int>> pq;
  pq.push({0, s});
  d[s] = 0;
  min_du[s] = du[s];
  min_dv[s] = dv[s];
  while (!pq.empty()) {
    int node = pq.top().second;
    pq.pop();
    if (min_du[node] + min_dv[node] == 14) cout << node << endl;
    if (vis[node]) continue;
    vis[node] = true;
    for (auto [child, w] : ad[node]) {
      long long new_du = min(min_du[node], du[child]);
      long long new_dv = min(min_dv[node], dv[child]);
      if (d[child] == d[node] + w && new_du + new_dv < min_du[child] + min_dv[child]) {
        min_du[child] = new_du;
        min_dv[child] = new_dv;
      } else if (d[child] > d[node] + w) {
        d[child] = d[node] + w;
        min_du[child] = new_du;
        min_dv[child] = new_dv;
        pq.push({-d[child], child});
      }
    }
  }
  cout << min(du[v], min_du[t] + min_dv[t]) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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