Submission #861436

#	Time	Username	Problem	Language	Result	Execution time	Memory
861436		NeroZein	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	254 ms	19584 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

using T = pair<long long, int>;

const int N = 1e5 + 5;
const long long INF = 1e16; 

int n, m;
vector<pair<int, int>> g[N]; 

vector<long long> dij(int src) {
  vector<long long> ret(n + 1, INF);
  ret[src] = 0;
  priority_queue<T, vector<T>, greater<T>> pq; 
  pq.emplace(0, src);
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    if (c != ret[v]) {
      continue;
    }
    for (auto [u, w] : g[v]) {
      if (w + c < ret[u]) {
        ret[u] = w + c;
        pq.emplace(ret[u], u); 
      }
    }
  }
  return ret; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  int s, t;
  cin >> s >> t;
  int qu, qv;
  cin >> qu >> qv; 
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w); 
  }
  vector<long long> ds = dij(s);
  vector<long long> dt = dij(t);
  vector<long long> dv = dij(qv);
  vector<long long> du = dij(qu);
  long long ans = du[qv];
  for (int rep = 0; rep < 2; ++rep) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1); 
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return ds[i] < ds[j]; 
    });
    vector<long long> dp(n + 1, INF); 
    for (int v : ord) {
      ans = min(ans, dp[v] + dv[v]); 
      for (auto [u, w] : g[v]) {
        if (ds[v] + w + dt[u] == ds[t]) {
          dp[u] = min({dp[u], dp[v], du[v]}); 
        }
      }
    }
    swap(qu, qv); 
    swap(du, dv); 
  }
  cout << ans << '\n'; 
  return 0;
}

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