oj.uz

Submission #976382

# Submission time Handle Problem Language Result Execution time Memory
976382 2024-05-06T13:50:13 Z LmaoLmao Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 297 ms 25104 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa= array<ll,3>; 

const int N = 1e6+5;
const int INF = 1e9;

ll sr[100001][2];
ll d[100001][2]; 
ll D[100001][2]; 
vector<ii> adj[100001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,s,t,u,v;
	cin >> n >> m;
	cin >> s >> t;
	cin >> u >> v;
	for(int i=0;i<m;i++) {
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	for(int i=1;i<=n;i++) {
		d[i][0]=(ll)1e15;
		d[i][1]=(ll)1e15;
		D[i][0]=(ll)1e15;
		D[i][1]=(ll)1e15;
		sr[i][0]=(ll)1e15;
		sr[i][1]=(ll)1e15;
	}
	priority_queue<aa,vector<aa>,greater<aa>> q;
	q.push({0,s,0});
	q.push({0,t,1});
	sr[s][0]=0;
	sr[t][1]=0;
	while(!q.empty()) {
		aa cur=q.top();
		q.pop();
		if(cur[0]>sr[cur[1]][cur[2]]) continue;
		for(ii to:adj[cur[1]]) {
			if(sr[to.fi][cur[2]]>sr[cur[1]][cur[2]]+to.se) {
				sr[to.fi][cur[2]]=sr[cur[1]][cur[2]]+to.se;
				q.push({sr[to.fi][cur[2]],to.fi,cur[2]});	
			}
		}
	}
	q.push({0,u,0});
	ll l=sr[t][0];
	d[u][0]=0;
	while(!q.empty()) {
		aa cur=q.top();
		q.pop();
		if(cur[0]>d[cur[1]][cur[2]]) continue;
		if(sr[cur[1]][0]+sr[cur[1]][1]==l && cur[2]==0) {
			queue<int> bfs;
			if(d[cur[1]][1]>d[cur[1]][0]) {
				d[cur[1]][1]=d[cur[1]][0];
				q.push({d[cur[1]][1],cur[1],1});
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][0]+to.se==sr[cur[1]][0] && d[to.fi][1]>cur[0]) {
					d[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({d[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][0]+to.se==sr[k][0] && d[to.fi][1]>d[k][1]) {
						d[to.fi][1]=d[k][1];
						bfs.push(to.fi);
						q.push({d[to.fi][1],to.fi,1}); 
					}
				}
			}
			for(ii to:adj[cur[1]]) {
				if(sr[to.fi][1]+to.se==sr[cur[1]][1] && d[to.fi][1]>cur[0]) {
					d[to.fi][1]=cur[0];
					bfs.push(to.fi);
					q.push({d[to.fi][1],to.fi,1}); 
				}
			}
			while(!bfs.empty()) {
				int k=bfs.front();
				bfs.pop();
				for(ii to:adj[k]) {
					if(sr[to.fi][1]+to.se==sr[k][1] && d[to.fi][1]>d[k][1]) {
						d[to.fi][1]=d[k][1];
						bfs.push(to.fi);
						q.push({d[to.fi][1],to.fi,1}); 
					}
				}
			}
		}
		for(ii to:adj[cur[1]]) {
			if(d[to.fi][cur[2]]>d[cur[1]][cur[2]]+to.se) {
				d[to.fi][cur[2]]=d[cur[1]][cur[2]]+to.se;
				q.push({d[to.fi][cur[2]],to.fi,cur[2]});	
			}
		}
	}
	cout << min(min(d[v][1],d[v][0]),min(D[u][1],D[u][0]));
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 25104 KB Output is correct
2 Correct 231 ms 21776 KB Output is correct
3 Correct 222 ms 22328 KB Output is correct
4 Correct 218 ms 22076 KB Output is correct
5 Correct 219 ms 22100 KB Output is correct
6 Correct 226 ms 24272 KB Output is correct
7 Correct 221 ms 21588 KB Output is correct
8 Correct 239 ms 21060 KB Output is correct
9 Correct 227 ms 21960 KB Output is correct
10 Correct 177 ms 20932 KB Output is correct
11 Correct 67 ms 14388 KB Output is correct
12 Correct 247 ms 22224 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 21140 KB Output is correct
2 Correct 236 ms 20932 KB Output is correct
3 Correct 266 ms 22320 KB Output is correct
4 Correct 243 ms 20984 KB Output is correct
5 Correct 258 ms 21744 KB Output is correct
6 Correct 235 ms 22212 KB Output is correct
7 Correct 256 ms 20904 KB Output is correct
8 Correct 255 ms 20936 KB Output is correct
9 Correct 297 ms 22516 KB Output is correct
10 Correct 240 ms 21444 KB Output is correct
11 Correct 77 ms 14284 KB Output is correct
12 Correct 231 ms 20964 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8028 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 12 ms 9564 KB Output is correct
5 Correct 6 ms 8024 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Incorrect 2 ms 6748 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 25104 KB Output is correct
2 Correct 231 ms 21776 KB Output is correct
3 Correct 222 ms 22328 KB Output is correct
4 Correct 218 ms 22076 KB Output is correct
5 Correct 219 ms 22100 KB Output is correct
6 Correct 226 ms 24272 KB Output is correct
7 Correct 221 ms 21588 KB Output is correct
8 Correct 239 ms 21060 KB Output is correct
9 Correct 227 ms 21960 KB Output is correct
10 Correct 177 ms 20932 KB Output is correct
11 Correct 67 ms 14388 KB Output is correct
12 Correct 247 ms 22224 KB Output is correct
13 Correct 264 ms 21140 KB Output is correct
14 Correct 236 ms 20932 KB Output is correct
15 Correct 266 ms 22320 KB Output is correct
16 Correct 243 ms 20984 KB Output is correct
17 Correct 258 ms 21744 KB Output is correct
18 Correct 235 ms 22212 KB Output is correct
19 Correct 256 ms 20904 KB Output is correct
20 Correct 255 ms 20936 KB Output is correct
21 Correct 297 ms 22516 KB Output is correct
22 Correct 240 ms 21444 KB Output is correct
23 Correct 77 ms 14284 KB Output is correct
24 Correct 231 ms 20964 KB Output is correct
25 Correct 7 ms 8028 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 2 ms 6748 KB Output is correct
28 Correct 12 ms 9564 KB Output is correct
29 Correct 6 ms 8024 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Incorrect 2 ms 6748 KB Output isn't correct
32 Halted 0 ms 0 KB -