Submission #947587

#	Time	Username	Problem	Language	Result	Execution time	Memory
947587		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	270 ms	25796 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>

vector<pii> graph[100003];
ll n,m,S,T,U,V,oo=1e9+1,min_dist;
ll dist[4][100003];
bool vis[2][100003];
ll wyn[2][100003];

void Dijkstra(ll st, ll par){
	fill(dist[par],dist[par]+n+1,oo);
	dist[par][st]=0;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,st});
	while(pq.size()){
		auto [d,v]=pq.top();
		pq.pop();
		for (auto [u,w] : graph[v]){
			if (d+w<dist[par][u]){
				dist[par][u]=d+w;
				pq.push({d+w,u});
			}
		}
	}
}

ll dfs(ll v, ll par){
	if (vis[par][v])return wyn[par][v];
	vis[par][v]=true;
	wyn[par][v]=dist[par][v];
	for (auto u : graph[v]){
		if (dist[2][u.first]+u.second+dist[3][v]==min_dist || dist[3][u.first]+u.second+dist[2][v]==min_dist){
			wyn[par][v]=min(wyn[par][v],dfs(u.first,par));
		}
	}
	return wyn[par][v];
}

void init(){
	cin >> n >> m >> S >> T >> U >> V;
	ll a,b,c;
	for (ll i = 1; i<=m; i++){
		cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({a,c});
	}
	Dijkstra(U,0);
	Dijkstra(V,1);
	Dijkstra(S,2);
	Dijkstra(T,3);
	min_dist=dist[2][T];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	init();
	ll ans=dist[0][V];
	for (ll i = 1; i<=n; i++){
		ans=min(ans,dfs(i,0)+dfs(i,1));
	}
	cout << ans << '\n';
}

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