Submission #1196798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196798		korticz	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	335 ms	22860 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100001;
int ve,ed,s,t,u,v,a,b,c,ans,distU[N],distV[N],distS[N],dp[2][N];
vector<pair<int,int>> adj[N];
bool visited[N];
struct edge{
	int weight,node,parent;
	bool operator<(const edge&other) const{
		return weight>other.weight;
	}
};
void dijkstra (int st,int dist[]) {
	dist[st]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,st});
	while(!pq.empty()) {
		auto[w,now]=pq.top();
		pq.pop();
		for (auto&[tow,to]:adj[now]) {
			if (dist[to]>tow+w) {
				dist[to]=tow+w;
				pq.push({tow+w,to});
			}
		}
	}
}

void dijkstra2 (int st,int en) {
	fill(dp[0],dp[0]+100001,LLONG_MAX/2);
	fill(dp[1],dp[1]+100001,LLONG_MAX/2);
	fill(visited,visited+100001,false);
	fill(distS,distS+N,LLONG_MAX/2);
	priority_queue<edge> pq;
	distS[st]=0;
	pq.push({0,st,0});
	while(!pq.empty()) {
		auto[w,now,par]=pq.top();
		pq.pop();
		if (w>distS[now]) continue;
		if (!visited[now]) {
			visited[now]=true;
			distS[now]=w;
			dp[0][now]=min(dp[0][par],distU[now]);
			dp[1][now]=min(dp[1][par],distV[now]);
			for (auto&[tow,to]:adj[now]) {
				if (distS[to]>=tow+w) {
					pq.push({tow+w,to,now});
				}
			}
		}
		else if (w==distS[now]) {
			int l=min(dp[0][par],distU[now]),r=min(dp[1][par],distV[now]);
			if (l+r<dp[0][now]+dp[1][now]) {
				dp[0][now]=l;
				dp[1][now]=r;
			}
		}
	}
	ans=min(ans,dp[0][en]+dp[1][en]);
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>ve>>ed>>s>>t>>u>>v;
	fill(distU,distU+100001,LLONG_MAX);
	fill(distV,distV+100001,LLONG_MAX);
	fill(distS,distS+100001,LLONG_MAX);
	for (int i=0;i<ed;i++) {
		cin>>a>>b>>c;
		adj[a].push_back({c,b});
		adj[b].push_back({c,a});
	}
	dijkstra(u,distU);
	dijkstra(v,distV);
	ans=distU[v];
	dijkstra2(s,t);
	dijkstra2(t,s);
	cout<<ans<<'\n';
	return 0;
}

/*
7 8 
4 6 
1 7
1 2 1
1 3 9
3 4 9
4 5 1
4 2 2
2 6 2
5 6 3
6 7 5
*/

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