Submission #865968

#	Time	Username	Problem	Language	Result	Execution time	Memory
865968		jhinezeal123	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	216 ms	26176 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const double eps = 0.000001;
const int mod = 1000000007;
const int N = 100001;
const int MATRIX_SIZE = 3;
int n,m,s,t,u,v,du[N],dv[N],ds[N],dpu[N],dpv[N];
vector <ii> G[N];
bool vi[N];
void Dijk(int x,int *dist){
	fill(dist+1,dist+n+1,1e18);
	dist[x]=0;
	priority_queue <ii,vector <ii>, greater <ii>> xet;
	xet.push({0,x});
	while (xet.size()){
		ii tam=xet.top();
		xet.pop();
		if (tam.fi>dist[tam.se]) continue;
		for (auto htc:G[tam.se]){
			if (dist[htc.fi]>htc.se+tam.fi){
				// cout<<htc.fi<<' '<<htc.se<<' '<<tam.fi<<endl;
				dist[htc.fi]=htc.se+tam.fi;
				xet.push({dist[htc.fi],htc.fi});
			}
		}
	}
	// dist[0]=2;
}
void Dp(){
	fill(ds+1,ds+n+1,1e18);
	ds[s]=0;
	fill(dpu,dpu+n+1,1e18);
	fill(dpv,dpv+n+1,1e18);
	dpu[s]=du[s];
	dpv[s]=dv[s];
	priority_queue <iii,vector <iii>,greater<iii>> xet;
	xet.push({0,{s,0}});
	while (xet.size()){
		iii tam=xet.top();
		int dist=tam.fi;
		int node=tam.se.fi;
		int par=tam.se.se;
		xet.pop();
		if (dist>ds[node]) continue;

		if (dpu[node]+dpv[node]>min(dpu[par],du[node])+min(dpv[par],dv[node])){
			dpu[node]=min(dpu[par],du[node]);
			dpv[node]=min(dpv[par],dv[node]);
		}
		// cout<<node<<' '<<dpu[node]<<' '<<dpv[node]<<' '<<par<<endl;
		if (!vi[node]){
			vi[node]=true;
			for (auto x:G[node]){
				if (ds[x.fi]>=x.se+dist){
					ds[x.fi]=x.se+dist;
					xet.push({ds[x.fi],{x.fi,node}});
				}
			}
		}
	}
}
void solve(){
	cin>>n>>m>>s>>t>>u>>v;
	for (int i=1,s1,s2,s3;i<=m;++i){
		cin>>s1>>s2>>s3;
		G[s2].push_back({s1,s3});
		G[s1].push_back({s2,s3});
	}
	Dijk(u,du);
	Dijk(v,dv);
	// cout<<du[3];
	// swap(t,s);
	Dp();
	cout<<min(dpu[t]+dpv[t],du[v]);
}
main() {
    //freopen("ok.inp","r",stdin);
	//freopen("ok.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    solve();
}

Compilation message (stderr)

commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main() {
      | ^~~~

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