Submission #595124

#	Time	Username	Problem	Language	Result	Execution time	Memory
595124		Vanilla	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	556 ms	26992 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;typedef long long z;const int q=1e5+2;vector<pair<int,z>> g[q];z d[3][q];z dp[2][q];bitset<q>vis;int main(){int n,m,s1,t1,s2,t2;cin >>n>>m>>s1>>t1>>s2>>t2;for(int i=0;i<q;i++)for(int j=0;j<3;j++)d[j][i]=1e18;for(int i=0;i<m;i++){int x,y,c;cin>>x>>y>>c;g[x].push_back({y,c});g[y].push_back({x,c});}auto o=[&](int b, int i) {set<pair<z,z>>s;d[i][b]=0;s.insert({0,b});while(!s.empty()){int u=s.begin()->second;s.erase(s.begin());for(auto &[v,c]:g[u]) {if(d[i][u]+c<d[i][v]) {s.erase({d[i][v],v});d[i][v]=d[i][u]+c;s.insert({d[i][v],v});}}}};o(s2,0);o(t2,1);o(s1,2);z rs=d[0][t2];auto r=[&](int u,auto&& r)->void{vis[u]=1;dp[0][u]=d[0][u];dp[1][u]=d[1][u];for(auto &[v,c]:g[u]){if(d[2][u]-c!=d[2][v])continue;if(!vis[v])r(v,r);dp[0][u]=min(dp[0][u],dp[0][v]);dp[1][u]=min(dp[1][u],dp[1][v]);}rs=min(rs,min(dp[0][u]+d[1][u],dp[1][u]+d[0][u]));};r(t1,r);cout<<rs<<"\n";return 0;}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45