oj.uz

답안 #754473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754473 2023-06-07T20:57:35 Z IvanJ Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 575 ms 33048 KB 
#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;
const ll inf = 1e18;

int n, m, s, t, u, v;
vector<pair<int, ll>> adj[maxn];
vector<int> G[maxn];
ll D[5][maxn];
ll mini[maxn];
int deg[maxn];

void get_dist(int X, int p) {
	vector<ll> dist(n, inf);
	dist[X] = 0;
	
	set<pair<ll, int>> q;
	q.insert({0, X});
	while(q.size()) {
		auto state = *q.begin();
		q.erase(state);
		int x = state.y;
		for(auto P : adj[x]) {
			int y = P.x;
			ll c = P.y;
			if(dist[y] == inf) {
				dist[y] = dist[x] + c;
				q.insert({dist[y], y});
			} else if(dist[x] + c < dist[y]) {
				q.erase({dist[y], y});
				dist[y] = dist[x] + c;
				q.insert({dist[y], y});
			}
		}
	}
	for(int i = 0;i < n;i++) 
		D[p][i] = dist[i];
}

vector<int> get_topo() {
	for(int i = 0;i < n;i++) 
		for(auto p : adj[i]) 
			if(D[0][t] == D[0][i] + p.y + D[1][p.x])
				G[i].pb(p.x), deg[p.x]++;
	
	queue<int> q;
	for(int i = 0;i < n;i++) 
		if(deg[i] == 0) q.push(i);
	
	vector<int> V;
	while(q.size()) {
		int x = q.front();
		q.pop(), V.pb(x);
		for(int y : G[x]) {
			deg[y]--;
			if(deg[y] == 0) 
				q.push(y);
		}
	}
	
	reverse(all(V));
	return V;
}

int main() {
	scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
	s--, t--, u--, v--;
	for(int i = 0;i < m;i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		x--, y--;
		adj[x].pb({y, c}), adj[y].pb({x, c});
	}
	
	get_dist(s, 0);
	get_dist(t, 1);
	get_dist(u, 2);
	get_dist(v, 3);
	
	vector<int> topo = get_topo();
	
	ll ans = inf;
	for(int x : topo) {
		mini[x] = D[3][x];
		for(int y : G[x]) 
			mini[x] = min(mini[x], mini[y]);
		
		ans = min(ans, D[2][x] + mini[x]);
	}
	
	for(int x : topo) {
		mini[x] = D[2][x];
		for(int y : G[x]) 
			mini[x] = min(mini[x], mini[y]);
		
		ans = min(ans, D[3][x] + mini[x]);
	}
	
	printf("%lld\n", ans);
	return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d%d", &x, &y, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 28460 KB Output is correct
2 Correct 535 ms 27944 KB Output is correct
3 Correct 499 ms 28072 KB Output is correct
4 Correct 482 ms 28484 KB Output is correct
5 Correct 415 ms 27888 KB Output is correct
6 Correct 558 ms 28536 KB Output is correct
7 Correct 465 ms 27748 KB Output is correct
8 Correct 481 ms 27948 KB Output is correct
9 Correct 454 ms 27688 KB Output is correct
10 Correct 328 ms 27824 KB Output is correct
11 Correct 210 ms 22036 KB Output is correct
12 Correct 478 ms 27320 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 516 ms 28148 KB Output is correct
2 Correct 519 ms 29328 KB Output is correct
3 Correct 575 ms 29116 KB Output is correct
4 Correct 459 ms 29192 KB Output is correct
5 Correct 482 ms 29096 KB Output is correct
6 Correct 477 ms 29184 KB Output is correct
7 Correct 508 ms 29516 KB Output is correct
8 Correct 501 ms 30064 KB Output is correct
9 Correct 518 ms 30192 KB Output is correct
10 Correct 509 ms 29128 KB Output is correct
11 Correct 140 ms 23976 KB Output is correct
12 Correct 407 ms 30424 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11476 KB Output is correct
2 Correct 6 ms 9788 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 19 ms 13104 KB Output is correct
5 Correct 15 ms 11476 KB Output is correct
6 Correct 6 ms 9848 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 6 ms 9756 KB Output is correct
10 Correct 12 ms 11388 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9708 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 7 ms 9720 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 28460 KB Output is correct
2 Correct 535 ms 27944 KB Output is correct
3 Correct 499 ms 28072 KB Output is correct
4 Correct 482 ms 28484 KB Output is correct
5 Correct 415 ms 27888 KB Output is correct
6 Correct 558 ms 28536 KB Output is correct
7 Correct 465 ms 27748 KB Output is correct
8 Correct 481 ms 27948 KB Output is correct
9 Correct 454 ms 27688 KB Output is correct
10 Correct 328 ms 27824 KB Output is correct
11 Correct 210 ms 22036 KB Output is correct
12 Correct 478 ms 27320 KB Output is correct
13 Correct 516 ms 28148 KB Output is correct
14 Correct 519 ms 29328 KB Output is correct
15 Correct 575 ms 29116 KB Output is correct
16 Correct 459 ms 29192 KB Output is correct
17 Correct 482 ms 29096 KB Output is correct
18 Correct 477 ms 29184 KB Output is correct
19 Correct 508 ms 29516 KB Output is correct
20 Correct 501 ms 30064 KB Output is correct
21 Correct 518 ms 30192 KB Output is correct
22 Correct 509 ms 29128 KB Output is correct
23 Correct 140 ms 23976 KB Output is correct
24 Correct 407 ms 30424 KB Output is correct
25 Correct 12 ms 11476 KB Output is correct
26 Correct 6 ms 9788 KB Output is correct
27 Correct 5 ms 9812 KB Output is correct
28 Correct 19 ms 13104 KB Output is correct
29 Correct 15 ms 11476 KB Output is correct
30 Correct 6 ms 9848 KB Output is correct
31 Correct 9 ms 9804 KB Output is correct
32 Correct 7 ms 9940 KB Output is correct
33 Correct 6 ms 9756 KB Output is correct
34 Correct 12 ms 11388 KB Output is correct
35 Correct 6 ms 9684 KB Output is correct
36 Correct 6 ms 9708 KB Output is correct
37 Correct 6 ms 9684 KB Output is correct
38 Correct 7 ms 9720 KB Output is correct
39 Correct 6 ms 9812 KB Output is correct
40 Correct 544 ms 33048 KB Output is correct
41 Correct 471 ms 30164 KB Output is correct
42 Correct 438 ms 30208 KB Output is correct
43 Correct 182 ms 25008 KB Output is correct
44 Correct 155 ms 25080 KB Output is correct
45 Correct 370 ms 31060 KB Output is correct
46 Correct 387 ms 31020 KB Output is correct
47 Correct 485 ms 31192 KB Output is correct
48 Correct 190 ms 24636 KB Output is correct
49 Correct 453 ms 32216 KB Output is correct
50 Correct 394 ms 30460 KB Output is correct
51 Correct 343 ms 30964 KB Output is correct