oj.uz

Submission #307529

# Submission time Handle Problem Language Result Execution time Memory
307529 2020-09-28T14:00:36 Z shivensinha4 Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 1312 ms 87860 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e5;
const ll INF = 1e15;
int n, m;
vector<pair<int, ll>> adj[MXN+1];
ll du[MXN+1], dv[MXN+1];
pair<ll, ll> df[MXN+1][3][3];

void dijk(int a, ll d[]) {
	for_(i, 0, n) d[i] = INF;
	d[a] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, a});
	
	while (pq.size()) {
		int p = pq.top().second; ll dist = pq.top().first; pq.pop();
		if (d[p] < dist) continue;
		for (auto i: adj[p]) if (d[i.first] > dist+i.second) {
			d[i.first] = dist+i.second;
			pq.push({d[i.first], i.first});
		}
	}
}


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
	s -= 1; t -= 1; u -= 1; v -= 1;
	for_(i, 0, m) {
		int a, b; ll w; cin >> a >> b >> w;
		a -= 1;  b -= 1;
		adj[a].push_back({b, w}); adj[b].push_back({a, w});
	}
	
	dijk(u, du); dijk(v, dv);
	
	for_(i, 0, n) {
		adj[i].push_back({i, 0});
		for_(j, 0, 2) for_(k, 0, 2) df[i][j][k] = {INF, INF};
	}
	
	priority_queue<pair<pair<ll, ll>, vi>, vector<pair<pair<ll, ll>, vi>>, greater<pair<pair<ll, ll>, vi>>> pq;
	pq.push({{0, 0}, {s, 0, 0}});
	
	ll ans = INF, bda = INF;
	while (pq.size()) {
		vi p = pq.top().second; 
		ll da = pq.top().first.first, db = pq.top().first.second; pq.pop();
		if (df[p[0]][p[1]][p[2]] < pair<ll, ll> {da, db}) continue;
		
		if (p == (vi) {t, 1, 1}) {
			if (da < bda) ans = db;
			else if (da == bda) ans = min(ans, db);
			bda = min(bda, da);
		}
		for (auto i: adj[p[0]]) {
			if (df[i.first][p[1]][p[2]] > pair<ll, ll> {da+i.second, db}) {
				df[i.first][p[1]][p[2]] = {da+i.second, db};
				pq.push({{da+i.second, db}, {i.first, p[1], p[2]}});
			}
			
			if (!p[1] and df[i.first][1][p[2]] > pair<ll, ll> {da+i.second, db+du[p[0]]}) {
				df[i.first][1][p[2]] = {da+i.second, db+du[p[0]]};
				pq.push({{da+i.second, db+du[p[0]]}, {i.first, 1, p[2]}});
			}
			
			if (!p[2] and df[i.first][p[1]][1] > pair<ll, ll> {da+i.second, db+dv[p[0]]}) {
				df[i.first][p[2]][1] = {da+i.second, db+dv[p[0]]};
				pq.push({{da+i.second, db+dv[p[0]]}, {i.first, p[1], 1}});
			}
		}
	}
	
	cout << min(ans, du[v]) << endl;

	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 87732 KB Output is correct
2 Correct 1120 ms 62092 KB Output is correct
3 Correct 1014 ms 59200 KB Output is correct
4 Correct 1119 ms 65576 KB Output is correct
5 Correct 1093 ms 59084 KB Output is correct
6 Correct 1312 ms 87860 KB Output is correct
7 Correct 1118 ms 60956 KB Output is correct
8 Correct 1133 ms 62104 KB Output is correct
9 Correct 1165 ms 59208 KB Output is correct
10 Correct 1137 ms 59060 KB Output is correct
11 Correct 405 ms 27324 KB Output is correct
12 Correct 1244 ms 59132 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 62488 KB Output is correct
2 Correct 1193 ms 59020 KB Output is correct
3 Correct 988 ms 59024 KB Output is correct
4 Correct 1069 ms 59012 KB Output is correct
5 Correct 1229 ms 59020 KB Output is correct
6 Correct 1024 ms 59096 KB Output is correct
7 Correct 923 ms 45964 KB Output is correct
8 Correct 1216 ms 59012 KB Output is correct
9 Correct 1020 ms 59168 KB Output is correct
10 Correct 1256 ms 59380 KB Output is correct
11 Correct 391 ms 27384 KB Output is correct
12 Correct 1016 ms 59264 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4992 KB Output is correct
2 Correct 3 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 41 ms 7036 KB Output is correct
5 Correct 13 ms 4352 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 5 ms 3200 KB Output is correct
8 Correct 6 ms 3200 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 12 ms 4224 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 3 ms 2816 KB Output is correct
13 Correct 4 ms 2944 KB Output is correct
14 Correct 4 ms 2944 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 87732 KB Output is correct
2 Correct 1120 ms 62092 KB Output is correct
3 Correct 1014 ms 59200 KB Output is correct
4 Correct 1119 ms 65576 KB Output is correct
5 Correct 1093 ms 59084 KB Output is correct
6 Correct 1312 ms 87860 KB Output is correct
7 Correct 1118 ms 60956 KB Output is correct
8 Correct 1133 ms 62104 KB Output is correct
9 Correct 1165 ms 59208 KB Output is correct
10 Correct 1137 ms 59060 KB Output is correct
11 Correct 405 ms 27324 KB Output is correct
12 Correct 1244 ms 59132 KB Output is correct
13 Correct 1251 ms 62488 KB Output is correct
14 Correct 1193 ms 59020 KB Output is correct
15 Correct 988 ms 59024 KB Output is correct
16 Correct 1069 ms 59012 KB Output is correct
17 Correct 1229 ms 59020 KB Output is correct
18 Correct 1024 ms 59096 KB Output is correct
19 Correct 923 ms 45964 KB Output is correct
20 Correct 1216 ms 59012 KB Output is correct
21 Correct 1020 ms 59168 KB Output is correct
22 Correct 1256 ms 59380 KB Output is correct
23 Correct 391 ms 27384 KB Output is correct
24 Correct 1016 ms 59264 KB Output is correct
25 Correct 23 ms 4992 KB Output is correct
26 Correct 3 ms 2944 KB Output is correct
27 Correct 4 ms 2944 KB Output is correct
28 Correct 41 ms 7036 KB Output is correct
29 Correct 13 ms 4352 KB Output is correct
30 Correct 4 ms 2944 KB Output is correct
31 Correct 5 ms 3200 KB Output is correct
32 Correct 6 ms 3200 KB Output is correct
33 Correct 5 ms 2944 KB Output is correct
34 Correct 12 ms 4224 KB Output is correct
35 Correct 3 ms 2816 KB Output is correct
36 Correct 3 ms 2816 KB Output is correct
37 Correct 4 ms 2944 KB Output is correct
38 Correct 4 ms 2944 KB Output is correct
39 Correct 4 ms 2944 KB Output is correct
40 Correct 1112 ms 87284 KB Output is correct
41 Correct 1127 ms 59108 KB Output is correct
42 Correct 1150 ms 59040 KB Output is correct
43 Correct 413 ms 27256 KB Output is correct
44 Correct 374 ms 27384 KB Output is correct
45 Correct 1032 ms 59168 KB Output is correct
46 Correct 834 ms 44724 KB Output is correct
47 Correct 1202 ms 63768 KB Output is correct
48 Correct 460 ms 27256 KB Output is correct
49 Correct 860 ms 87028 KB Output is correct
50 Correct 926 ms 59064 KB Output is correct
51 Correct 887 ms 59048 KB Output is correct