제출 #963177

#제출 시각아이디문제언어결과실행 시간메모리
963177HuyATCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
243 ms22496 KiB
#include<bits/stdc++.h> const int MaxN = 1e5 + 10; const long long Inf = 1e18; struct Data{ long long vertex,w; bool operator > (const Data &other) const{ return (w > other.w); } }; std::vector<std::pair<int,int>> adj[MaxN + 1]; int n,m; long long f[4][MaxN + 1],s,t,s1,t1,ans = Inf; std::pair<long long,long long> minPath[MaxN + 1],minPath1[MaxN + 1]; bool vis[MaxN + 1]; void readData(){ std::cin >> n >> m >> s >> t >> s1 >> t1; for(int i = 1;i <= m;++i){ int u,v,w; std::cin >> u >> v >> w; adj[u].emplace_back(v,w); adj[v].emplace_back(u,w); } } void disjktra(int source,long long dist[]){ std::fill(dist + 1,dist + n + 1,Inf); std::priority_queue<Data,std::vector<Data>,std::greater<Data>> pq; pq.push({source,0}); dist[source] = 0; while(!pq.empty()){ Data t = pq.top(); pq.pop(); if(t.w > dist[t.vertex]){ continue; } for(std::pair<int,int> v : adj[t.vertex]){ if(t.w + v.second < dist[v.first]){ dist[v.first] = t.w + v.second; pq.push({v.first,dist[v.first]}); } } } } void disjktra1(){ std::fill(f[3] + 1,f[3] + n + 1,Inf); for(int i = 1;i <= n;++i){ minPath[i] = {f[1][i],f[2][i]}; minPath1[i] = {f[2][i],f[1][i]}; } std::priority_queue<Data,std::vector<Data>,std::greater<Data>> pq; pq.push({s,0}); f[3][s] = 0; while(!pq.empty()){ Data t = pq.top(); pq.pop(); if(t.w > f[3][t.vertex]){ continue; } for(std::pair<int,int> v : adj[t.vertex]){ if(t.w + v.second < f[3][v.first]){ f[3][v.first] = t.w + v.second; pq.push({v.first,f[3][v.first]}); std::pair<long long,long long> first = {std::min(f[1][v.first],minPath[t.vertex].first),std::min(f[2][v.first],minPath[t.vertex].second)}; std::pair<long long,long long> second = {std::min(f[2][v.first],minPath1[t.vertex].first),std::min(f[1][v.first],minPath1[t.vertex].second)}; minPath[v.first] = first; minPath1[v.first] = second; // assert(std::min(first.first,first.second) > 0); // assert(std::min(second.first,second.second) > 0); } if(t.w + v.second == f[3][v.first]){ std::pair<long long,long long> first = {std::min(f[1][v.first],minPath[t.vertex].first),std::min(f[2][v.first],minPath[t.vertex].second)}; std::pair<long long,long long> second = {std::min(f[2][v.first],minPath1[t.vertex].first),std::min(f[1][v.first],minPath1[t.vertex].second)}; minPath[v.first] = std::min(minPath[v.first],first); minPath1[v.first] = std::min(minPath1[v.first],second); } } } } void dfs(int u = t){ vis[u] = true; ans = std::min(ans,minPath[u].first + minPath[u].second); ans = std::min(ans,minPath1[u].first + minPath1[u].second); for(std::pair<int,int> v : adj[u]){ if(f[3][v.first] + v.second == f[3][u] && !vis[v.first]){ dfs(v.first); } } } int main(){ std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);std::cout.tie(nullptr); readData(); disjktra(s1,f[1]); disjktra(t1,f[2]); disjktra1(); dfs(); ans = std::min(ans,f[2][s1]); std::cout << ans; 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...