oj.uz

Submission #947584

# Submission time Handle Problem Language Result Execution time Memory
947584 2024-03-16T13:48:27 Z 4QT0R Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 284 ms 20908 KB 
#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)+dist[1][i],dfs(i,1)+dist[0][i]});
	}
	cout << ans << '\n';
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 19332 KB Output is correct
2 Correct 284 ms 19628 KB Output is correct
3 Correct 227 ms 20908 KB Output is correct
4 Correct 194 ms 20032 KB Output is correct
5 Correct 214 ms 20592 KB Output is correct
6 Correct 219 ms 19524 KB Output is correct
7 Correct 240 ms 20712 KB Output is correct
8 Correct 219 ms 20332 KB Output is correct
9 Incorrect 118 ms 17928 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 20244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4188 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 19332 KB Output is correct
2 Correct 284 ms 19628 KB Output is correct
3 Correct 227 ms 20908 KB Output is correct
4 Correct 194 ms 20032 KB Output is correct
5 Correct 214 ms 20592 KB Output is correct
6 Correct 219 ms 19524 KB Output is correct
7 Correct 240 ms 20712 KB Output is correct
8 Correct 219 ms 20332 KB Output is correct
9 Incorrect 118 ms 17928 KB Output isn't correct
10 Halted 0 ms 0 KB -