Submission #467116

#	Time	Username	Problem	Language	Result	Execution time	Memory
467116		Autron	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	519 ms	31692 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m;
int s, t;
int u, v;

vector<vector<pair<int, int>>> g;

void dijkstra(int src, vector<int> &dist, vector<vector<int>> &par){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i=1;i<=n;++i) dist[i]=1e18;
	dist[src]=0;
	pq.push({dist[src], src});
	while(!pq.empty()){
		int x, d;
		tie(d, x)=pq.top();
		pq.pop();
		if(d!=dist[x]) continue;
		for(auto it:g[x]){
			int nx=it.first, nd=it.second+d;
			if(nd<dist[nx]){
				pq.push({nd, nx});
				dist[nx]=nd;
				par[nx].clear();
				par[nx].push_back(x);
			}
			else if(nd==dist[nx]){
				par[nx].push_back(x);
			}
		}
	}
}

void dijkstra(int src, vector<int> &dist){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i=1;i<=n;++i) dist[i]=1e18;
	dist[src]=0;
	pq.push({dist[src], src});
	while(!pq.empty()){
		int x, d;
		tie(d, x)=pq.top();
		pq.pop();
		if(d!=dist[x]) continue;
		for(auto it:g[x]){
			int nx=it.first, nd=it.second+d;
			if(nd<dist[nx]){
				pq.push({nd, nx});
				dist[nx]=nd;
			}
		}
	}
}

void dfs(int x, vector<vector<int>> &out, vector<int> &dp, vector<int> &dist){
	dp[x]=dist[x];
	for(auto it:out[x]){
		if(dp[it]==-1) dfs(it, out, dp, dist);
		dp[x]=min(dp[x], dp[it]);
	}
}

int32_t main(){
	cin>>n>>m>>s>>t>>u>>v;
	g.resize(n+1);
	vector<vector<int>> par(n+1), rpar(n+1);;
	vector<int> dists(n+1), distu(n+1), distv(n+1);
	vector<int> dpf(n+1, -1), dpb(n+1, -1);
	for(int i=1;i<=m;++i){
		int a, b, c;
		cin>>a>>b>>c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dijkstra(u, distu);
	dijkstra(v, distv);
	dijkstra(s, dists, par);
	queue<int> q;
	vector<bool> used(n+1, 0);
	q.push(t);
	used[t]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto it:par[x]){
			rpar[it].push_back(x);
			if(used[it]) continue;
			used[it]=1;
			q.push(it);
		}
	}
	dfs(s, rpar, dpf, distu);
	dfs(t, par, dpb, distu);
	int sol=distu[v];
	for(int i=1;i<=n;++i){
		if(!used[i]) continue;
		sol=min(sol, distv[i]+min(dpf[i], dpb[i]));
	}
	cout<<sol<<"\n";
}

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