제출 #928576

#제출 시각아이디문제언어결과실행 시간메모리
928576AlphaMale06Commuter Pass (JOI18_commuter_pass)C++17
15 / 100
279 ms37020 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define F first #define S second const int N = 1e5+5; const int inf = 1e16; vector<pair<int, int>> adj[N]; int dist[N][4]; bool mark[N]; int dp[N][2]; int sp; int ans; void dijkstra(int s, int t){ for(int i=0; i< N; i++){ mark[i]=0; dist[i][t]=inf; } dist[s][t]=0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while(pq.size()){ auto p = pq.top(); pq.pop(); if(mark[p.S] || dist[p.S][t]<p.F)continue; mark[p.S]=1; for(auto to : adj[p.S]){ if(!mark[to.F] && to.S+dist[p.S][t]<dist[to.F][t]){ dist[to.F][t]=to.S+dist[p.S][t]; pq.push({dist[to.F][t], to.F}); } } } } int cnt=0; void dfs(int v, int p, int t){ cnt++; assert(cnt<1000000); dp[v][0]=min(dp[p][0], dist[v][2]); dp[v][1]=min(dp[p][1], dist[v][3]); ans=min(ans, dp[v][0]+dp[v][1]); for(auto to : adj[v]){ if(to.F!=p){ if(dist[v][t]+dist[to.F][t^1]+to.S==sp){ dfs(to.F, v, t); } } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i=0; i< m; i++){ int a, b, c; cin >> a >> b >> c; adj[a].pb({b, c}); adj[b].pb({a, c}); } dijkstra(s, 0); dijkstra(t, 1); dijkstra(u, 2); dijkstra(v, 3); sp=dist[s][1]; ans=dist[v][2]; dp[0][0]=inf; dp[0][1]=inf; dfs(s, 0, 0); dfs(t, 0, 1); 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...