oj.uz

Submission #467116

# Submission time Handle Problem Language Result Execution time Memory
467116 2021-08-21T18:06:50 Z Autron Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 519 ms 31692 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m;
int s, t;
int u, v;

vector<vector<pair<int, int>>> g;

void dijkstra(int src, vector<int> &dist, vector<vector<int>> &par){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i=1;i<=n;++i) dist[i]=1e18;
	dist[src]=0;
	pq.push({dist[src], src});
	while(!pq.empty()){
		int x, d;
		tie(d, x)=pq.top();
		pq.pop();
		if(d!=dist[x]) continue;
		for(auto it:g[x]){
			int nx=it.first, nd=it.second+d;
			if(nd<dist[nx]){
				pq.push({nd, nx});
				dist[nx]=nd;
				par[nx].clear();
				par[nx].push_back(x);
			}
			else if(nd==dist[nx]){
				par[nx].push_back(x);
			}
		}
	}
}

void dijkstra(int src, vector<int> &dist){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for(int i=1;i<=n;++i) dist[i]=1e18;
	dist[src]=0;
	pq.push({dist[src], src});
	while(!pq.empty()){
		int x, d;
		tie(d, x)=pq.top();
		pq.pop();
		if(d!=dist[x]) continue;
		for(auto it:g[x]){
			int nx=it.first, nd=it.second+d;
			if(nd<dist[nx]){
				pq.push({nd, nx});
				dist[nx]=nd;
			}
		}
	}
}

void dfs(int x, vector<vector<int>> &out, vector<int> &dp, vector<int> &dist){
	dp[x]=dist[x];
	for(auto it:out[x]){
		if(dp[it]==-1) dfs(it, out, dp, dist);
		dp[x]=min(dp[x], dp[it]);
	}
}

int32_t main(){
	cin>>n>>m>>s>>t>>u>>v;
	g.resize(n+1);
	vector<vector<int>> par(n+1), rpar(n+1);;
	vector<int> dists(n+1), distu(n+1), distv(n+1);
	vector<int> dpf(n+1, -1), dpb(n+1, -1);
	for(int i=1;i<=m;++i){
		int a, b, c;
		cin>>a>>b>>c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dijkstra(u, distu);
	dijkstra(v, distv);
	dijkstra(s, dists, par);
	queue<int> q;
	vector<bool> used(n+1, 0);
	q.push(t);
	used[t]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto it:par[x]){
			rpar[it].push_back(x);
			if(used[it]) continue;
			used[it]=1;
			q.push(it);
		}
	}
	dfs(s, rpar, dpf, distu);
	dfs(t, par, dpb, distu);
	int sol=distu[v];
	for(int i=1;i<=n;++i){
		if(!used[i]) continue;
		sol=min(sol, distv[i]+min(dpf[i], dpb[i]));
	}
	cout<<sol<<"\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 25728 KB Output is correct
2 Correct 441 ms 25212 KB Output is correct
3 Correct 510 ms 31248 KB Output is correct
4 Correct 416 ms 25300 KB Output is correct
5 Correct 440 ms 26048 KB Output is correct
6 Correct 428 ms 25652 KB Output is correct
7 Correct 453 ms 26344 KB Output is correct
8 Correct 445 ms 26076 KB Output is correct
9 Correct 434 ms 24760 KB Output is correct
10 Correct 414 ms 24684 KB Output is correct
11 Correct 208 ms 25920 KB Output is correct
12 Correct 440 ms 29036 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 27184 KB Output is correct
2 Correct 473 ms 27592 KB Output is correct
3 Correct 501 ms 26972 KB Output is correct
4 Correct 519 ms 27368 KB Output is correct
5 Correct 502 ms 28160 KB Output is correct
6 Correct 463 ms 30660 KB Output is correct
7 Correct 466 ms 31444 KB Output is correct
8 Correct 445 ms 27440 KB Output is correct
9 Correct 458 ms 28100 KB Output is correct
10 Correct 457 ms 27124 KB Output is correct
11 Correct 211 ms 26180 KB Output is correct
12 Correct 463 ms 31148 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1792 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 44 ms 3812 KB Output is correct
5 Correct 22 ms 1968 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 22 ms 1988 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 304 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 25728 KB Output is correct
2 Correct 441 ms 25212 KB Output is correct
3 Correct 510 ms 31248 KB Output is correct
4 Correct 416 ms 25300 KB Output is correct
5 Correct 440 ms 26048 KB Output is correct
6 Correct 428 ms 25652 KB Output is correct
7 Correct 453 ms 26344 KB Output is correct
8 Correct 445 ms 26076 KB Output is correct
9 Correct 434 ms 24760 KB Output is correct
10 Correct 414 ms 24684 KB Output is correct
11 Correct 208 ms 25920 KB Output is correct
12 Correct 440 ms 29036 KB Output is correct
13 Correct 464 ms 27184 KB Output is correct
14 Correct 473 ms 27592 KB Output is correct
15 Correct 501 ms 26972 KB Output is correct
16 Correct 519 ms 27368 KB Output is correct
17 Correct 502 ms 28160 KB Output is correct
18 Correct 463 ms 30660 KB Output is correct
19 Correct 466 ms 31444 KB Output is correct
20 Correct 445 ms 27440 KB Output is correct
21 Correct 458 ms 28100 KB Output is correct
22 Correct 457 ms 27124 KB Output is correct
23 Correct 211 ms 26180 KB Output is correct
24 Correct 463 ms 31148 KB Output is correct
25 Correct 23 ms 1792 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 44 ms 3812 KB Output is correct
29 Correct 22 ms 1968 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 3 ms 460 KB Output is correct
32 Correct 4 ms 588 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 22 ms 1988 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 296 KB Output is correct
38 Correct 2 ms 304 KB Output is correct
39 Correct 2 ms 332 KB Output is correct
40 Correct 416 ms 29284 KB Output is correct
41 Correct 433 ms 29012 KB Output is correct
42 Correct 439 ms 29340 KB Output is correct
43 Correct 228 ms 28612 KB Output is correct
44 Correct 248 ms 28432 KB Output is correct
45 Correct 483 ms 31640 KB Output is correct
46 Correct 463 ms 31636 KB Output is correct
47 Correct 435 ms 29208 KB Output is correct
48 Correct 211 ms 25284 KB Output is correct
49 Correct 388 ms 29840 KB Output is correct
50 Correct 506 ms 30888 KB Output is correct
51 Correct 475 ms 31692 KB Output is correct