Submission #1181251

#TimeUsernameProblemLanguageResultExecution timeMemory
1181251Godgift42Commuter Pass (JOI18_commuter_pass)C++20
31 / 100
541 ms21220 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ //ios_base::sync_with_stdio(0); //cin.tie(0); int n,m; cin >> n >> m; int s,t,u,v; cin >> s >> t >> u >> v; s--;t--;u--;v--; vector<vector<pair<int,ll>>> adj(n); for(int i=0;i<m;i++){ int a,b; ll c; cin >> a >> b >> c; a--;b--; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } vector<ll> du(n,10000000000000000); vector<ll> dv(n,10000000000000000); vector<bool> vis(n); priority_queue<pair<ll,int>> pq; du[u]=0; pq.push({0,u}); while(!pq.empty()){ int cr=pq.top().second; pq.pop(); if(!vis[cr]){ vis[cr]=true; for(auto [ch,w]:adj[cr]){ if(!vis[ch] and du[ch]>du[cr]+w){ du[ch]=du[cr]+w; pq.push({-du[ch],ch}); } } } } for(int i=0;i<n;i++)vis[i]=false; dv[v]=0; pq.push({0,v}); while(!pq.empty()){ int cr=pq.top().second; pq.pop(); if(!vis[cr]){ vis[cr]=true; for(auto [ch,w]:adj[cr]){ if(!vis[ch] and dv[ch]>dv[cr]+w){ dv[ch]=dv[cr]+w; pq.push({-dv[ch],ch}); } } } } ll ans=du[v]; for(int i=0;i<n;i++)vis[i]=false; vector<vector<ll>> dp(2,vector<ll>(n,1000000000000000000)); vector<ll> dist(n,1000000000000000000); priority_queue<pair<ll,pair<int,int>>> qp; qp.push({0,{s,s}}); dist[s]=0; dp[0][s]=du[s]; dp[1][s]=dv[s]; while(!qp.empty()){ int node=qp.top().second.first; int par=qp.top().second.second; ll cd=qp.top().first; qp.pop(); if(!vis[node]){ vis[node]=true; dp[0][node]=min(du[node],min(dp[0][par],dp[0][node])); dp[1][node]=min(dv[node],min(dp[1][par],dp[1][node])); for(auto [ch,w]:adj[node]){ if(dist[ch]>=dist[node]+w){ dist[ch]=dist[node]+w; qp.push({-dist[ch],{ch,node}}); } } } else if(-cd==dist[node]){ dp[0][node]=min(du[node],min(dp[0][par],dp[0][node])); dp[1][node]=min(dv[node],min(dp[1][par],dp[1][node])); } } ans=min(ans,dp[0][t]+dp[1][t]); for(int i=0;i<n;i++){ dist[i]=1000000000000000000; vis[i]=false; dp[0][i]=1000000000000000000; dp[1][i]=1000000000000000000; } dist[t]=0; qp.push({0,{t,t}}); dp[0][t]=du[t]; dp[1][t]=dv[t]; while(!qp.empty()){ int node=qp.top().second.first; int par=qp.top().second.second; ll cd=qp.top().first; qp.pop(); if(!vis[node]){ vis[node]=true; dp[0][node]=min(du[node],min(dp[0][par],dp[0][node])); dp[1][node]=min(dv[node],min(dp[1][par],dp[1][node])); for(auto [ch,w]:adj[node]){ if(dist[ch]>=dist[node]+w){ dist[ch]=dist[node]+w; qp.push({-dist[ch],{ch,node}}); } } } else if(-cd==dist[node]){ dp[0][node]=min(du[node],min(dp[0][par],dp[0][node])); dp[1][node]=min(dv[node],min(dp[1][par],dp[1][node])); } } ans=min(ans,dp[0][s]+dp[1][s]); 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...