oj.uz

답안 #315329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
315329 2020-10-22T13:43:25 Z aZvezda Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 397 ms 24740 KB 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
  
const ll MAX_N = 1e5 + 10;
ll dist[4][MAX_N];
vector<pair<ll, ll> > g[MAX_N];
ll dp[MAX_N][4];
ll n, m;

void dij(ll ind, ll start) {
	for(ll i = 0; i < MAX_N; i ++) {
		dist[ind][i] = mod;
	}
	dist[ind][start] = 0;
	priority_queue<pair<ll, ll> > pq;
	pq.push({0, start});
	while(!pq.empty()) {
		auto curr = pq.top(); pq.pop();
		curr.first *= -1;
		if(curr.first != dist[ind][curr.second]) {continue;}
		for(auto it : g[curr.second]) {
			if(dist[ind][it.first] > curr.first + it.second) {
				dist[ind][it.first] = curr.first + it.second;
				pq.push({-dist[ind][it.first], it.first});
			}
		}
	}
}

vector<ll> can;  

bool cmp(ll a, ll b) {
	return dist[2][a] < dist[2][b];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	ll s, t, u, v;
	cin >> s >> t >> u >> v;
	for(ll i = 0; i < m; i ++) {
		ll a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dij(0, u);
	dij(1, v);
	dij(2, s);
	dij(3, t);
	ll minPath = dist[2][t];
	for(ll i = 1; i <= n; i ++) {
		for(ll j = 0; j < 4; j ++) {
			dp[i][j] = mod;
		}
		if(dist[2][i] + dist[3][i] == minPath) {
			can.push_back(i);
		}
	}    
	dp[s][0] = 0;
	sort(can.begin(), can.end(), cmp);
	for(auto it : can) {
		for(auto prv : g[it]) {
			if(dist[2][prv.first] + prv.second + dist[3][it] == minPath) {
				for(ll mask = 0; mask < 4; mask ++) {
					chkmin(dp[it][mask], dp[prv.first][mask]);
				}
			}
		}
		for(ll mask = 0; mask < 4; mask ++) {
			if(!(mask & 1)) {
				chkmin(dp[it][mask + 1], dp[it][mask] + dist[0][it]);
			}
			if(!(mask & 2)) {				
				chkmin(dp[it][mask + 2], dp[it][mask] + dist[1][it]);
			}
		}
	}
	cout << min(dp[t][3], dist[0][v]) << endl;
    return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 20636 KB Output is correct
2 Correct 365 ms 21004 KB Output is correct
3 Correct 363 ms 21708 KB Output is correct
4 Correct 349 ms 23636 KB Output is correct
5 Correct 356 ms 22536 KB Output is correct
6 Correct 352 ms 21748 KB Output is correct
7 Correct 361 ms 22516 KB Output is correct
8 Correct 376 ms 22720 KB Output is correct
9 Correct 337 ms 21996 KB Output is correct
10 Correct 308 ms 22508 KB Output is correct
11 Correct 149 ms 16624 KB Output is correct
12 Correct 356 ms 23916 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 363 ms 20768 KB Output is correct
2 Correct 371 ms 20988 KB Output is correct
3 Correct 376 ms 20700 KB Output is correct
4 Correct 370 ms 20728 KB Output is correct
5 Correct 372 ms 20860 KB Output is correct
6 Correct 370 ms 21204 KB Output is correct
7 Correct 385 ms 23328 KB Output is correct
8 Correct 397 ms 22376 KB Output is correct
9 Correct 372 ms 22632 KB Output is correct
10 Correct 378 ms 22432 KB Output is correct
11 Correct 160 ms 16884 KB Output is correct
12 Correct 363 ms 24116 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7544 KB Output is correct
2 Correct 5 ms 5888 KB Output is correct
3 Correct 4 ms 5888 KB Output is correct
4 Correct 19 ms 9216 KB Output is correct
5 Correct 12 ms 7552 KB Output is correct
6 Correct 5 ms 5888 KB Output is correct
7 Correct 5 ms 6016 KB Output is correct
8 Correct 6 ms 6076 KB Output is correct
9 Correct 5 ms 5888 KB Output is correct
10 Correct 12 ms 7552 KB Output is correct
11 Correct 4 ms 5888 KB Output is correct
12 Correct 4 ms 5888 KB Output is correct
13 Correct 4 ms 5888 KB Output is correct
14 Correct 5 ms 5888 KB Output is correct
15 Correct 5 ms 5888 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 384 ms 20636 KB Output is correct
2 Correct 365 ms 21004 KB Output is correct
3 Correct 363 ms 21708 KB Output is correct
4 Correct 349 ms 23636 KB Output is correct
5 Correct 356 ms 22536 KB Output is correct
6 Correct 352 ms 21748 KB Output is correct
7 Correct 361 ms 22516 KB Output is correct
8 Correct 376 ms 22720 KB Output is correct
9 Correct 337 ms 21996 KB Output is correct
10 Correct 308 ms 22508 KB Output is correct
11 Correct 149 ms 16624 KB Output is correct
12 Correct 356 ms 23916 KB Output is correct
13 Correct 363 ms 20768 KB Output is correct
14 Correct 371 ms 20988 KB Output is correct
15 Correct 376 ms 20700 KB Output is correct
16 Correct 370 ms 20728 KB Output is correct
17 Correct 372 ms 20860 KB Output is correct
18 Correct 370 ms 21204 KB Output is correct
19 Correct 385 ms 23328 KB Output is correct
20 Correct 397 ms 22376 KB Output is correct
21 Correct 372 ms 22632 KB Output is correct
22 Correct 378 ms 22432 KB Output is correct
23 Correct 160 ms 16884 KB Output is correct
24 Correct 363 ms 24116 KB Output is correct
25 Correct 12 ms 7544 KB Output is correct
26 Correct 5 ms 5888 KB Output is correct
27 Correct 4 ms 5888 KB Output is correct
28 Correct 19 ms 9216 KB Output is correct
29 Correct 12 ms 7552 KB Output is correct
30 Correct 5 ms 5888 KB Output is correct
31 Correct 5 ms 6016 KB Output is correct
32 Correct 6 ms 6076 KB Output is correct
33 Correct 5 ms 5888 KB Output is correct
34 Correct 12 ms 7552 KB Output is correct
35 Correct 4 ms 5888 KB Output is correct
36 Correct 4 ms 5888 KB Output is correct
37 Correct 4 ms 5888 KB Output is correct
38 Correct 5 ms 5888 KB Output is correct
39 Correct 5 ms 5888 KB Output is correct
40 Correct 339 ms 23164 KB Output is correct
41 Correct 351 ms 23832 KB Output is correct
42 Correct 350 ms 23880 KB Output is correct
43 Correct 177 ms 17260 KB Output is correct
44 Correct 178 ms 17260 KB Output is correct
45 Correct 360 ms 24740 KB Output is correct
46 Correct 352 ms 24488 KB Output is correct
47 Correct 347 ms 23376 KB Output is correct
48 Correct 177 ms 16620 KB Output is correct
49 Correct 292 ms 22964 KB Output is correct
50 Correct 345 ms 24428 KB Output is correct
51 Correct 336 ms 24616 KB Output is correct