제출 #654303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654303		lunchbox1	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	382 ms	20780 KiB

commuter_pass

/*
 Commuter Pass
 https://oj.uz/problem/view/JOI18_commuter_pass
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

template<class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

const int N = 1e5;
const LL INF = 1e18;

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n, m; cin >> n >> m;
 int s, t, u, v; cin >> s >> t >> u >> v, s--, t--, u--, v--;
 static vector<pair<int, int>> g[N];
 while (m--) {
  int i, j, c; cin >> i >> j >> c, i--, j--;
  g[i].push_back({j, c}), g[j].push_back({i, c});
 }
 auto gen = [&](int s, LL *dt) {
  min_pq<pair<LL, int>> q;
  fill(dt, dt + n, INF);
  q.push({dt[s] = 0, s});
  while (!q.empty()) {
   auto [d, i] = q.top(); q.pop();
   if (d != dt[i]) continue;
   for (auto [j, c] : g[i])
    if (d + c < dt[j])
     q.push({dt[j] = d + c, j});
  }
 };
 static LL ds[N], dt[N];
 gen(s, ds), gen(t, dt);
 static LL f[N][3];
 LL all = ds[t];
 for (int i = 0; i < n; i++) f[i][0] = f[i][1] = f[i][2] = INF;
 min_pq<tuple<LL, int, int>> q;
 q.push({f[u][0] = 0, u, 0});
 while (!q.empty()) {
  auto [d, i, t] = q.top(); q.pop();
  if (d != f[i][t]) continue;
  for (auto [j, c] : g[i]) {
   if ((t == 0 || t == 1) && (ds[i] + dt[j] + c == all || dt[i] + ds[j] + c == all) && d < f[j][1])
    q.push({f[j][1] = d, j, 1});
   if (t == 0 && d + c < f[j][0])
    q.push({f[j][0] = d + c, j, 0});
   if ((t == 1 || t == 2) && d + c < f[j][2])
    q.push({f[j][2] = d + c, j, 2});
  }
 }
 cout << min({f[v][0], f[v][1], f[v][2]}) << '\n';
 return 0;
}

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