제출 #237806

#제출 시각아이디문제언어결과실행 시간메모리
237806aggu_01000101Commuter Pass (JOI18_commuter_pass)C++14
0 / 100
1131 ms262148 KiB
#include <bits/stdc++.h> #define int long long #define INF 10000000000000000 #define lchild(i) (i*2 + 1) #define rchild(i) (i*2 + 2) #define mid(l, u) ((l+u)/2) #define MOD 1000000007 using namespace std; int n, m, s, t, u, v, sp; vector<pair<int, int>> adj[100005]; vector<int> opte[100005]; bool visited[100005]; int dp[100005]; void dij(int start, int arr[]){ for(int i = 1;i<=n;i++) arr[i] = INF; arr[start] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); while(!pq.empty()){ pair<int, int> curr = pq.top(); pq.pop(); if(curr.first != arr[curr.second]) continue; for(pair<int, int> j: adj[curr.second]){ if((j.second + curr.first)>arr[j.first]) continue; arr[j.first] = j.second + curr.first; pq.push({arr[j.first], j.first}); } } } void dfs(int x){ if(visited[x]) return; visited[x] = true; for(int j: opte[x]){ dfs(j); dp[x] = min(dp[x], dp[j]); } } int findans(int a1[], int a2[]){ for(int i = 1;i<=n;i++){ visited[i] = false; dp[i] = a2[i]; } for(int i = 1;i<=n;i++){ dfs(i); } int ans = INF; for(int i = 1;i<=n;i++){ ans = min(ans, dp[i] + a1[i]); } return ans; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m>>s>>t>>u>>v; for(int i = 0;i<m;i++){ int a, b, c; cin>>a>>b>>c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } int sd[n+1], td[n+1], ud[n+1], vd[n+1]; dij(s, sd); dij(t, td); dij(u, ud); dij(v, vd); sp = sd[t]; int ans = ud[v]; for(int i = 1;i<=n;i++){ for(pair<int, int> j: adj[i]){ if (sd[i] + j.second + td[j.first] == sp){ opte[i].push_back(j.first); opte[j.first].push_back(i); } } } ans = min(ans, findans(ud, vd)); ans = min(ans, findans(vd, ud)); cout<<ans<<"\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...