제출 #1089730

#제출 시각아이디문제언어결과실행 시간메모리
1089730serpent_121Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
288 ms25488 KiB
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <unordered_map> #include <set> #include <queue> #include <numeric> #include <cmath> #include <cstring> #include <climits> #include <stack> #include <math.h> #include <iomanip> #include <bitset> typedef long long ll; using namespace std; using vi = vector<int>; using T = pair<ll,int>; #define fst first #define snd second #define pll pair<ll,ll> #define pi pair<int,int> #define triple pair<pair<ll,ll>,ll> #define pb push_back #define all(x) (x).begin(), (x).end() // JOI 2018 // https://oj.uz/problem/view/JOI18_commuter_pass const ll MAXN = 1e5 +1; const ll INF = LLONG_MAX; vector<ll> dist_t(MAXN,INF); vector<ll> dist_s(MAXN,INF); vector<ll> dist_u(MAXN,INF); vector<ll> dist_v(MAXN,INF); vector<ll> dp_u(MAXN,INF); vector<ll> dp_v(MAXN,INF); vector<pair<int, ll>> adj[MAXN]; vector<ll> order_s; vector<ll> order_t; ll s, t; vector<ll> opt; void dijkstra(int source, vector<ll> &dist, bool record_order, vector<ll> &order = opt) { priority_queue<T,vector<T>, greater<T>> pq; pq.push({0,source}); dist[source] = 0; while (!pq.empty()) { auto temp = pq.top(); pq.pop(); int node = temp.snd; ll cdist = temp.fst; if (cdist > dist[node]) continue; if (record_order) order.pb(node); for (auto &[next, w] : adj[node]) { if (dist[node] + w < dist[next]) { dist[next] = dist[node] + w; pq.push({dist[next],next}); } } } } bool onpath(int v) { // on a shortest path from s to t? return (dist_s[v] + dist_t[v] == dist_t[s]); } int main () { ll n, m; cin >> n >> m; cin >> s >> t; ll u, v; cin >> u >> v; for (int i = 0; i<m; i++) { ll a, b, c; cin >> a >> b >> c; adj[a].pb({b,c}); adj[b].pb({a,c}); } dijkstra(s, dist_s, true, order_s); dijkstra(t, dist_t, false); dijkstra(u, dist_u, false); dijkstra(v, dist_v, false); dp_u[s] = dist_u[s]; dp_v[s] = dist_v[s]; for (auto vert : order_s) { if (!onpath(vert)) continue; dp_u[vert] = dist_u[vert]; dp_v[vert] = dist_v[vert]; for (auto &[nb, w] : adj[vert]) { if (dist_s[nb] + w == dist_s[vert]) { dp_u[vert] = min(dp_u[vert], dp_u[nb]); dp_v[vert] = min(dp_v[vert], dp_v[nb]); } } } ll ans = dist_u[v]; for (int i =1; i<=n; i++) { if (onpath(i)) { ans = min(ans, dist_u[i] + dp_v[i]); ans = min(ans, dist_v[i] + dp_u[i]); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...