Submission #976358

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976358	2024-05-06T13:19:42 Z	LmaoLmao	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	304 ms	23908 KB

commuter_pass

#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];
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;
		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;
			d[cur[1]][1]=min(d[cur[1]][1],d[cur[1]][0]);
			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(d[v][1],d[v][0]);
    return 0;
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	22692 KB	Output is correct
2	Correct	247 ms	19396 KB	Output is correct
3	Correct	213 ms	19904 KB	Output is correct
4	Correct	219 ms	19396 KB	Output is correct
5	Correct	245 ms	20680 KB	Output is correct
6	Correct	223 ms	23908 KB	Output is correct
7	Correct	226 ms	19412 KB	Output is correct
8	Correct	235 ms	20668 KB	Output is correct
9	Correct	261 ms	19392 KB	Output is correct
10	Correct	170 ms	19392 KB	Output is correct
11	Correct	80 ms	12636 KB	Output is correct
12	Correct	238 ms	20700 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	19400 KB	Output is correct
2	Correct	267 ms	19400 KB	Output is correct
3	Correct	271 ms	19312 KB	Output is correct
4	Correct	245 ms	19400 KB	Output is correct
5	Correct	240 ms	20032 KB	Output is correct
6	Correct	243 ms	19964 KB	Output is correct
7	Correct	246 ms	20676 KB	Output is correct
8	Correct	243 ms	20424 KB	Output is correct
9	Correct	304 ms	19444 KB	Output is correct
10	Correct	243 ms	19408 KB	Output is correct
11	Correct	99 ms	12836 KB	Output is correct
12	Correct	235 ms	20680 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5980 KB	Output is correct
2	Correct	1 ms	4700 KB	Output is correct
3	Correct	1 ms	4696 KB	Output is correct
4	Correct	11 ms	7512 KB	Output is correct
5	Correct	6 ms	5980 KB	Output is correct
6	Correct	2 ms	4700 KB	Output is correct
7	Incorrect	3 ms	4700 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	22692 KB	Output is correct
2	Correct	247 ms	19396 KB	Output is correct
3	Correct	213 ms	19904 KB	Output is correct
4	Correct	219 ms	19396 KB	Output is correct
5	Correct	245 ms	20680 KB	Output is correct
6	Correct	223 ms	23908 KB	Output is correct
7	Correct	226 ms	19412 KB	Output is correct
8	Correct	235 ms	20668 KB	Output is correct
9	Correct	261 ms	19392 KB	Output is correct
10	Correct	170 ms	19392 KB	Output is correct
11	Correct	80 ms	12636 KB	Output is correct
12	Correct	238 ms	20700 KB	Output is correct
13	Correct	239 ms	19400 KB	Output is correct
14	Correct	267 ms	19400 KB	Output is correct
15	Correct	271 ms	19312 KB	Output is correct
16	Correct	245 ms	19400 KB	Output is correct
17	Correct	240 ms	20032 KB	Output is correct
18	Correct	243 ms	19964 KB	Output is correct
19	Correct	246 ms	20676 KB	Output is correct
20	Correct	243 ms	20424 KB	Output is correct
21	Correct	304 ms	19444 KB	Output is correct
22	Correct	243 ms	19408 KB	Output is correct
23	Correct	99 ms	12836 KB	Output is correct
24	Correct	235 ms	20680 KB	Output is correct
25	Correct	7 ms	5980 KB	Output is correct
26	Correct	1 ms	4700 KB	Output is correct
27	Correct	1 ms	4696 KB	Output is correct
28	Correct	11 ms	7512 KB	Output is correct
29	Correct	6 ms	5980 KB	Output is correct
30	Correct	2 ms	4700 KB	Output is correct
31	Incorrect	3 ms	4700 KB	Output isn't correct
32	Halted	0 ms	0 KB	-