제출 #703067

#제출 시각아이디문제언어결과실행 시간메모리
703067speedyArdaCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
643 ms31536 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int MAXN = 1e5+5; const ll INF = 1e18; bool visited[MAXN]; ll dpU[MAXN], dpV[MAXN], dp[2][MAXN], dpS[MAXN], ans = 2e18; //int par[MAXN]; vector< vector< pair<long long, long long > > > adj(MAXN); void dijkstra1(int v, ll arr[]) { fill(visited, visited + MAXN, false); priority_queue< pair<ll, ll > > pq; pq.push({0LL, v}); while(!pq.empty()) { pair<ll, ll> curr = pq.top(); pq.pop(); if(!visited[curr.second]) { arr[curr.second] = -curr.first; visited[curr.second] = true; for(pair<ll, ll> e : adj[curr.second]) pq.push({curr.first - e.first, e.second}); } } } void dijkstra2(int start, int end) { fill(dp[0], dp[0] + MAXN, INF); fill(dp[1], dp[1] + MAXN, INF); fill(visited, visited + MAXN, false); priority_queue< pair<ll, pair<ll, ll> > > pq; pq.push({0, {start, 0}}); dp[0][0] = dp[1][0] = INF; while(!pq.empty()) { pair<ll, pair<ll, ll> > curr = pq.top(); pq.pop(); ll node = curr.second.first; ll dist = curr.first; ll par = curr.second.second; if(!visited[node]) { dpS[node] = -dist; visited[node] = true; dp[0][node] = min(dp[0][par], dpU[node]); dp[1][node] = min(dp[1][par], dpV[node]); for(pair<ll, ll> e : adj[node]) { pq.push({dist - e.first, {e.second, node}}); } } else if(dpS[node] == -dist) { if(min(dpU[node], dp[0][par]) + min(dpV[node], dp[1][par]) <= dp[0][node] + dp[1][node]) { dp[0][node] = min(dp[0][par], dpU[node]); dp[1][node] = min(dp[1][par], dpV[node]); } } } ans = min(ans, dp[0][end] + dp[1][end]); } int main() { int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i = 1; i <= m; i++) { ll a, b, c; cin >> a >> b >> c; adj[a].push_back({c, b}); adj[b].push_back({c, a}); } dijkstra1(u, dpU); dijkstra1(v, dpV); ans = dpU[v]; dijkstra2(s, t); dijkstra2(t, s); cout << ans << "\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...