제출 #714542

#제출 시각아이디문제언어결과실행 시간메모리
714542tcmmichaelb139Commuter Pass (JOI18_commuter_pass)C++17
0 / 100
2080 ms27796 KiB
#include "bits/stdc++.h" using namespace std; struct node { int v; long long dist, mtu, mtv; bool operator<(const node &rhs) const { if (dist == rhs.dist) return mtu + mtv < rhs.mtu + rhs.mtv; return dist < rhs.dist; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N, M, S, T, U, V; cin >> N >> M >> S >> T >> U >> V; vector<pair<int, long long>> adj[N + 1]; for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } auto distcalc = [&](int s) { priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q; vector<long long> dist(N + 1, 1e18); vector<bool> vis(N + 1); q.push({0, s}); while (!q.empty()) { pair<long long, int> v = q.top(); q.pop(); if (vis[v.second]) continue; vis[v.second] = true; dist[v.second] = v.first; for (auto u : adj[v.second]) { q.push({u.second + v.first, u.first}); } } return dist; }; vector<long long> fu = distcalc(U), fv = distcalc(V); priority_queue<node> q; vector<long long> dist(N + 1, 1e18); q.push({S, 0, min((long long)1e18, fu[S]), min((long long)1e18, fv[S])}); long long bt = -1, ans = 1e18; while (!q.empty()) { node v = q.top(); q.pop(); if (v.v == T) { if (bt == -1) bt = v.dist; if (bt == v.dist) ans = min(ans, v.mtu + v.mtv); } if (dist[v.v] < v.dist) continue; dist[v.v] = v.dist; for (auto u : adj[v.v]) { q.push({u.first, v.dist + u.second, min(v.mtu, fu[u.first]), min(v.mtv, fv[u.first])}); } } cout << min(ans, fu[V]) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...