제출 #681780

#제출 시각아이디문제언어결과실행 시간메모리
681780zeroesandonesCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
424 ms31548 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef long double ld; typedef vector<ll> vi; typedef pair<ll, ll> pi; #define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i) #define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i) #define nl "\n" #define sp " " #define all(x) (x).begin(), (x).end() #define sc second #define fr first #define pb emplace_back struct edge { ll b, w; }; const ll mxN = 1e5 + 5; ll n, m; vector<edge> adj[mxN]; vi distU, distV; vi djik(ll x) { vi dist(n + 1, 1e15); bool vis[n + 1] = {}; priority_queue<pi> pq; dist[x] = 0; pq.emplace(0, x); while(!pq.empty()) { ll u = pq.top().sc; pq.pop(); if(vis[u]) continue; vis[u] = true; for(auto [v, w] : adj[u]) { if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.emplace(-dist[v], v); } } } return dist; } ll solve(ll start, ll end) { ll dp[2][100001]; bool visited[100001]; ll ds[100001]; fill(dp[0], dp[0] + 100001, LLONG_MAX / 2); fill(dp[1], dp[1] + 100001, LLONG_MAX / 2); fill(ds, ds + 100001, LLONG_MAX / 2); fill(visited, visited + 100001, false); priority_queue<pair<ll, pair<ll, ll>>> pq; pq.push({0, {start, 0}}); dp[0][0] = dp[1][0] = LLONG_MAX/ 2; while (!pq.empty()) { ll c, node, par; pair<ll, ll> p; tie(c, p) = pq.top(); tie(node, par) = p; pq.pop(); if (!visited[node]) { visited[node] = true; ds[node] = -c; dp[0][node] = min(distU[node], dp[0][par]); dp[1][node] = min(distV[node], dp[1][par]); for (auto i : adj[node]) pq.push({c - i.w, {i.b, node}}); } else if (-c == ds[node]) { if (min(distU[node], dp[0][par]) + min(distV[node], dp[1][par]) <= dp[0][node] + dp[1][node]) { dp[0][node] = min(distU[node], dp[0][par]); dp[1][node] = min(distV[node], dp[1][par]); } } } return dp[0][end] + dp[1][end]; } void solve() { cin >> n >> m; ll s, t; cin >> s >> t; ll u, v; cin >> u >> v; FOR(i, 0, m) { ll a, b, c; cin >> a >> b >> c; edge curr; curr.b = b; curr.w = c; adj[a].pb(curr); curr.b = a; adj[b].pb(curr); } distU = djik(u); distV = djik(v); ll ans = distU[v]; ll v1 = solve(s, t); ll v2 = solve(t, s); ans = min({ans, v1, v2}); cout << ans << nl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...