제출 #1010024

#제출 시각아이디문제언어결과실행 시간메모리
1010024SG2AlokCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
2069 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(NULL); #define fi first #define se second const ll MOD = 998244353; const ll INF = 1e18; // dp[i][0] = par -> child, dp[i][1] = child -> par ll n, m, s, t, u, V, dp[100005][2]; vector<pair<ll, ll>> adj[100005]; vector<ll> p[100005], child[100005]; bool vis[100005]; vector<ll> dijkstra(ll start){ vector<ll> dist(n + 2, INF); priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, start}); dist[start] = 0; while(!pq.empty()){ auto now = pq.top(); pq.pop(); if(dist[now.se] < now.fi) continue; for(auto v: adj[now.se]){ if(dist[v.fi] < now.fi + v.se) continue; dist[v.fi] = now.fi + v.se; pq.push({dist[v.fi], v.fi}); } } return dist; } void dfs1(ll u, vector<ll> distV){ if(dp[u][0] != INF) return; dp[u][0] = distV[u]; for(auto v: p[u]){ dfs1(v, distV); dp[u][0] = min(dp[u][0], dp[v][0]); } } void dfs2(ll u, vector<ll> distV){ if(dp[u][1] != INF) return; dp[u][1] = distV[u]; for(auto v: child[u]){ dfs2(v, distV); dp[u][1] = min(dp[u][1], dp[v][1]); } } int main(){ hitaf cin >> n >> m; cin >> s >> t; cin >> u >> V; for(int i = 1; i <= m; i++){ ll x, y, w; cin >> x >> y >> w; adj[x].push_back({y, w}); adj[y].push_back({x,w}); } vector<ll> dist = dijkstra(s); vector<ll> distU = dijkstra(u); vector<ll> distV = dijkstra(V); queue<ll> q; q.push(t); while(!q.empty()){ ll now = q.front(); q.pop(); for(auto v: adj[now]){ if(dist[v.fi] + v.se == dist[now]){ p[now].push_back(v.fi); child[v.fi].push_back(now); if(vis[v.fi]) continue; vis[v.fi] = true; q.push(v.fi); } } } for(int i = 1; i <= n; i++) dp[i][1] = dp[i][0] = INF; ll ans = distU[V]; for(int i = 1; i <= n; i++){ dfs1(i, distV); dfs2(i, distV); } for(int i = 1; i <= n; i++){ if(!p[i].empty() || !child[i].empty()){ ans = min(ans, distU[i] + min(dp[i][0], dp[i][1])); } } //cout << dp[1][1] << endl; cout << ans << endl; } /* 7 1 2 9 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...