제출 #782882

#제출 시각아이디문제언어결과실행 시간메모리
782882acatmeowmeowCommuter Pass (JOI18_commuter_pass)C++11
100 / 100
238 ms27160 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int n, m, s, t, u, v, f[N], se[N], mn[N], mn2[N], ans[N], dist[N]; vector<pair<int, int>> adj[N]; void path(int s, int dist[]) { dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (pq.size()) { int p = pq.top().first, u = pq.top().second; pq.pop(); if (p != dist[u]) continue; for (auto&x : adj[u]) { int v = x.first, c = x.second; if (dist[v] <= dist[u] + c) continue; dist[v] = dist[u] + c; pq.push({dist[v], v}); } } } void solve() { for (int i = 1; i <= n; i++) dist[i] = mn[i] = mn2[i] = ans[i] = 1e18; dist[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (pq.size()) { int p = pq.top().first, u = pq.top().second; pq.pop(); if (p != dist[u]) continue; mn[u] = min(mn[u], f[u]); mn2[u] = min(mn2[u], se[u]); for (auto&x : adj[u]) { int v = x.first, c = x.second; if (dist[v] + c == dist[u]) { mn[u] = min(mn[u], mn[v]); mn2[u] = min(mn2[u], mn2[v]); ans[u] = min(ans[u], ans[v]); } else if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pq.push({dist[v], v}); } } ans[u] = min({ans[u], se[u] + mn[u], f[u] + mn2[u]}); } cout << min({ans[t], f[v]}) << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> s >> t >> u >> v; for (int i = 1;i <= m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); } for (int i = 1;i <= n; i++) f[i] = se[i] = 1e18; path(u, f); path(v, se); solve(); 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...