제출 #782788

#제출 시각아이디문제언어결과실행 시간메모리
782788acatmeowmeowCommuter Pass (JOI18_commuter_pass)C++11
15 / 100
943 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define int long long vector<int> path(int n, int s, vector<vector<pair<int, int>>>&adj) { vector<int> dist(n + 5, 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; 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}); } } return dist; } void solve(int n, int s, int t, int u, int v, vector<vector<pair<int, int>>>&adj, vector<int>&f, vector<int>&se) { vector<int> dist(n + 5, 1e18), mn(n + 5, 1e18), ans(n + 5, 1e18), mn2(n + 5, 1e18), ans2(n + 5, 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]) continue; mn[u] = min(mn[u], mn[v]); ans[u] = min(ans[u], ans[v]); mn2[u] = min(mn2[u], mn2[v]); ans2[u] = min(ans2[u], ans2[v]); } ans[u] = min(ans[u], se[u] + mn[u]); ans2[u] = min(ans2[u], f[u] + mn2[u]); 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}); } } cout << min({ans[t], ans2[t], f[v]}) << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int s, t; cin >> s >> t; int u, v; cin >> u >> v; vector<vector<pair<int, int>>> adj(n + 5); 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}); } vector<int> f = path(n, u, adj), se = path(n, v, adj); solve(n, s, t, u, v, adj, f, se); 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...