Submission #517098

#TimeUsernameProblemLanguageResultExecution timeMemory
517098status_codingCommuter Pass (JOI18_commuter_pass)C++14
31 / 100
658 ms29140 KiB
#include <bits/stdc++.h> using namespace std; long long n,m,s,t,a,b,ans; vector<pair<long long, long long>> v[100005]; long long len[100005][4]; pair<long long, long long> dp[100005]; void djikstra(int s, int nr) { for(int i=1;i<=n;i++) len[i][nr] = 1e18; multiset<pair<long long, long long>> mul; mul.insert({0, s}); while(!mul.empty()) { long long p = mul.begin()->second; long long val = mul.begin()->first; mul.erase(mul.begin()); if(len[p][nr] != 1e18) continue; len[p][nr] = val; for(auto it : v[p]) { if(len[it.first][nr] != 1e18) continue; mul.insert({val + it.second, it.first}); } } } void calcDp(int p) { if(dp[p] != make_pair((long long)1e18, (long long)1e18)) return; dp[p] = {len[p][1], len[p][2]}; for(auto it : v[p]) if(len[p][0] - it.second == len[it.first][0]) { calcDp(it.first); dp[p].first = min(dp[p].first, dp[it.first].first); dp[p].second = min(dp[p].second, dp[it.first].second); } ans=min(ans, dp[p].first + dp[p].second); } int main() { cin>>n>>m>>s>>t>>a>>b; for(int i=1;i<=m;i++) { int x, y, c; cin>>x>>y>>c; v[x].push_back({y, c}); v[y].push_back({x, c}); } djikstra(t, 0); djikstra(b, 1); djikstra(a, 2); ans = len[a][1]; for(int i=1;i<=n;i++) dp[i] = {1e18, 1e18}; calcDp(s); 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...