제출 #861436

#제출 시각아이디문제언어결과실행 시간메모리
861436NeroZeinCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
254 ms19584 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...