제출 #1046639

#제출 시각아이디문제언어결과실행 시간메모리
1046639VMaksimoski008Commuter Pass (JOI18_commuter_pass)C++17
100 / 100
197 ms22836 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int maxn = 1e5 + 5; int n, m, S, T, U, V; vector<pii> graph[maxn+5]; vector<int> G[maxn+5]; vector<array<int, 3> > edges; ll dist[3][maxn+5]; void D(int s, int t) { priority_queue<pll, vector<pll>, greater<pll> > pq; for(int i=1; i<=n; i++) dist[t][i] = 1e18; dist[t][s] = 0; pq.push({ 0, s }); while(!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if(d != dist[t][u]) continue; for(auto &[v, w] : graph[u]) { if(dist[t][v] > d + w) { dist[t][v] = d + w; pq.push({ d + w, v }); } } } } int main() { cin >> n >> m >> S >> T >> U >> V; for(int i=0; i<m; i++) { int a, b, w; cin >> a >> b >> w; edges.push_back({ a, b, w }); graph[a].push_back({ b, w }); graph[b].push_back({ a, w }); } D(S, 0); D(U, 1); D(V, 2); vector<int> in(n+1), topo; queue<int> q; for(auto &[a, b, w] : edges) { if(dist[0][a] + w == dist[0][b]) G[a].push_back(b), in[b]++; if(dist[0][b] + w == dist[0][a]) G[b].push_back(a), in[a]++; } q.push(S); while(!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for(int &v : G[u]) if(--in[v] == 0) q.push(v); } vector<ll> dpU(n+1, 1e18), dpV(n+1, 1e18), dp(n+1, 1e18); dpU[S] = dist[1][S]; dpV[S] = dist[2][S]; dp[S] = dpU[S] + dpV[S]; for(int &u : topo) { dp[u] = min({ dp[u], dpU[u] + dist[2][u], dpV[u] + dist[1][u] }); for(int &v : G[u]) { dp[v] = min(dp[v], dp[u]); dpU[v] = min({ dpU[v], dpU[u], dist[1][v] }); dpV[v] = min({ dpV[v], dpV[u], dist[2][v] }); } } cout << min(dp[T], dist[1][V]) << '\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...