제출 #947591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947591		4QT0R	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	285 ms	25824 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=1e18+1,min_dist;
ll dist[4][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 (wyn[par][v]<oo)return wyn[par][v];
	wyn[par][v]=dist[0][v];
	for (auto u : graph[v]){
		if (dist[par+2][v]+u.second+dist[(par^1)+2][u.first]==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];
	fill(wyn[0],wyn[0]+n+1,oo);
	fill(wyn[1],wyn[1]+n+1,oo);
}

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

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

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