oj.uz

Submission #947587

# Submission time Handle Problem Language Result Execution time Memory
947587 2024-03-16T13:53:47 Z 4QT0R Commuter Pass (JOI18_commuter_pass) C++17
0 / 100
 270 ms 25796 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)+dfs(i,1));
	}
	cout << ans << '\n';
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 21992 KB Output is correct
2 Correct 232 ms 19736 KB Output is correct
3 Correct 253 ms 20928 KB Output is correct
4 Correct 214 ms 20804 KB Output is correct
5 Correct 251 ms 20416 KB Output is correct
6 Correct 201 ms 21004 KB Output is correct
7 Correct 247 ms 20812 KB Output is correct
8 Correct 250 ms 20780 KB Output is correct
9 Incorrect 75 ms 18044 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 20244 KB Output is correct
2 Correct 240 ms 23628 KB Output is correct
3 Correct 225 ms 23508 KB Output is correct
4 Correct 236 ms 24320 KB Output is correct
5 Correct 262 ms 23472 KB Output is correct
6 Correct 209 ms 25488 KB Output is correct
7 Correct 251 ms 25796 KB Output is correct
8 Correct 218 ms 23164 KB Output is correct
9 Correct 216 ms 23500 KB Output is correct
10 Correct 270 ms 23804 KB Output is correct
11 Incorrect 36 ms 14936 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 21992 KB Output is correct
2 Correct 232 ms 19736 KB Output is correct
3 Correct 253 ms 20928 KB Output is correct
4 Correct 214 ms 20804 KB Output is correct
5 Correct 251 ms 20416 KB Output is correct
6 Correct 201 ms 21004 KB Output is correct
7 Correct 247 ms 20812 KB Output is correct
8 Correct 250 ms 20780 KB Output is correct
9 Incorrect 75 ms 18044 KB Output isn't correct
10 Halted 0 ms 0 KB -