oj.uz

답안 #475704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475704 2021-09-23T17:26:34 Z thiago_bastos Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 380 ms 27152 KB 
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const i64 inf = 1e16L;

int n, m, s, t, u, v;
vector<ii> edge;
vector<vector<int>> g, dag;
vector<i64> ds, du, dv, dp;
vector<int> state;
i64 ans = inf;

auto dijkstra(int s) {
	vector<bool> seen(n, false);
	vector<i64> dist(n, inf);
	priority_queue<pair<i64, int>> pq;
	
	dist[s] = 0;
	pq.emplace(0LL, s);
	
	while(!pq.empty()) {
		auto [cst, v] = pq.top();
		pq.pop();
		if(seen[v]) continue;
		cst *= -1;
		seen[v] = true;
		for(int id : g[v]) {
			auto [u, w] = edge[id];
			if(dist[u] <= cst + w) continue;
			dist[u] = cst + w;
			pq.emplace(-dist[u], u);
		}
	}
	
	return dist;
}

vector<int> topo;

void dfs(int u) {
	state[u] = 0;

	if(u != t) {
		for(int id : dag[u]) {
			auto [v, w] = edge[id];
			
			if(state[v] == -1) dfs(v);
		
			if(state[v] == 1) {
				dp[u] = min(dp[u], dp[v]);
				state[u] = 1;
			}
		}
	}
	
	if(u == t) state[u] = 1;
	
	if(state[u] == 1) {
		dp[u] = min(dp[u], dv[u]);	
		ans = min(ans, du[u] + dp[u]);
		topo.push_back(u);
	}

}

void solve() {
	
	cin >> n >> m >> s >> t >> u >> v;
	
	--s, --t, --u, --v;
	
	edge.resize(2 * m);
	g.resize(n);
	dag.resize(n);
	state.assign(n, -1);
	dp.assign(n, inf);
	
	for(int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		
		--a, --b;
		
		edge[2 * i] = {b, c};
		edge[2 * i + 1] = {a, c};
		
		g[a].push_back(2 * i);
		g[b].push_back(2 * i + 1);
	}

	ds = dijkstra(s);
	du = dijkstra(u);
	dv = dijkstra(v);
	
	for(int u = 0; u < n; ++u) {
		for(int id : g[u]) {
			auto [v, w] = edge[id];
			if(ds[v] == ds[u] + w) dag[u].push_back(id);
		}
	}

	dfs(s);
	
	ans = min(ans, du[v]);
	
	fill(dp.begin(), dp.end(), inf);
	
	reverse(topo.begin(), topo.end());
	
	for(int v : topo) {
		dp[v] = dv[v];
		for(int id : g[v]) {
			auto [u, w] = edge[id];
			ans = min(ans, du[v] + dp[u]);
			dp[v] = min(dp[v], dp[u]);
		}
	}
	
	cout << ans << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 22908 KB Output is correct
2 Correct 319 ms 21784 KB Output is correct
3 Correct 340 ms 27152 KB Output is correct
4 Correct 296 ms 22704 KB Output is correct
5 Correct 360 ms 22480 KB Output is correct
6 Correct 323 ms 22932 KB Output is correct
7 Correct 327 ms 22504 KB Output is correct
8 Correct 326 ms 22636 KB Output is correct
9 Correct 311 ms 22064 KB Output is correct
10 Correct 255 ms 21972 KB Output is correct
11 Correct 150 ms 22204 KB Output is correct
12 Correct 329 ms 22264 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 23108 KB Output is correct
2 Correct 318 ms 23344 KB Output is correct
3 Correct 361 ms 23084 KB Output is correct
4 Correct 380 ms 23412 KB Output is correct
5 Correct 311 ms 23848 KB Output is correct
6 Correct 330 ms 26472 KB Output is correct
7 Correct 322 ms 26856 KB Output is correct
8 Correct 312 ms 23324 KB Output is correct
9 Correct 345 ms 23920 KB Output is correct
10 Correct 301 ms 23068 KB Output is correct
11 Correct 141 ms 22724 KB Output is correct
12 Correct 379 ms 26752 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1356 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 15 ms 2496 KB Output is correct
5 Correct 8 ms 1356 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 8 ms 1356 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 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 305 ms 22908 KB Output is correct
2 Correct 319 ms 21784 KB Output is correct
3 Correct 340 ms 27152 KB Output is correct
4 Correct 296 ms 22704 KB Output is correct
5 Correct 360 ms 22480 KB Output is correct
6 Correct 323 ms 22932 KB Output is correct
7 Correct 327 ms 22504 KB Output is correct
8 Correct 326 ms 22636 KB Output is correct
9 Correct 311 ms 22064 KB Output is correct
10 Correct 255 ms 21972 KB Output is correct
11 Correct 150 ms 22204 KB Output is correct
12 Correct 329 ms 22264 KB Output is correct
13 Correct 331 ms 23108 KB Output is correct
14 Correct 318 ms 23344 KB Output is correct
15 Correct 361 ms 23084 KB Output is correct
16 Correct 380 ms 23412 KB Output is correct
17 Correct 311 ms 23848 KB Output is correct
18 Correct 330 ms 26472 KB Output is correct
19 Correct 322 ms 26856 KB Output is correct
20 Correct 312 ms 23324 KB Output is correct
21 Correct 345 ms 23920 KB Output is correct
22 Correct 301 ms 23068 KB Output is correct
23 Correct 141 ms 22724 KB Output is correct
24 Correct 379 ms 26752 KB Output is correct
25 Correct 8 ms 1356 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 15 ms 2496 KB Output is correct
29 Correct 8 ms 1356 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 460 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 8 ms 1356 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 332 KB Output is correct
38 Correct 2 ms 332 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 275 ms 23368 KB Output is correct
41 Correct 324 ms 21980 KB Output is correct
42 Correct 287 ms 22020 KB Output is correct
43 Correct 148 ms 22216 KB Output is correct
44 Correct 152 ms 22144 KB Output is correct
45 Correct 325 ms 23056 KB Output is correct
46 Correct 328 ms 22784 KB Output is correct
47 Correct 371 ms 22752 KB Output is correct
48 Correct 152 ms 19576 KB Output is correct
49 Correct 275 ms 23040 KB Output is correct
50 Correct 307 ms 22756 KB Output is correct
51 Correct 312 ms 22932 KB Output is correct