oj.uz

답안 #388669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388669 2021-04-12T14:24:16 Z S2speed Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 551 ms 36920 KB 
#include<bits/stdc++.h>
#include<fstream>
 
using namespace std;
 
#pragma GCC optimize ("Ofast")
 
#define all(x) x.begin() , x.end()
#define mp make_pair
#define gcd __gcd
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<pii , int> piii;
typedef pair<pll , pll> pllll;
 
const ll maxn = 2e5 + 16 , md = 1e9 + 7 , inf = 2e18;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll n , m , a[4];
ll dis[maxn][4] , dp[maxn][2] , ans = inf;
priority_queue<pll , vector<pll> , greater<pll>> pq;
vector<pll> adj[maxn] , o;
vector<ll> sdj[maxn];
bitset<maxn> mark;

void dij(ll j){
	mark.reset();
	dis[a[j]][j] = 0;
	pq.push({0 , a[j]});
	while(!pq.empty()){
		pll p = pq.top(); pq.pop();
		ll v = p.second;
		if(mark[v]) continue;
		mark[v] = true;
		for(auto p : adj[v]){
			ll i = p.first , w = p.second;
			if(dis[i][j] < dis[v][j] + w) continue;
			dis[i][j] = dis[v][j] + w;
			pq.push({dis[i][j] , i});
		}
	}
	return;
}

int main(){ // check MAXN
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(dis , 63 , sizeof(dis));
	cin>>n>>m>>a[0]>>a[1]>>a[2]>>a[3]; a[0]--; a[1]--; a[2]--; a[3]--;
	for(ll i = 0 ; i < m ; i++){
		ll v , u , w;
		cin>>v>>u>>w; v--; u--;
		adj[v].push_back({u , w}); adj[u].push_back({v , w});
	}
	for(ll j = 0 ; j < 4 ; j++){
		dij(j);
	}
	for(ll v = 0 ; v < n ; v++){
		for(auto p : adj[v]){
			ll i = p.first , w = p.second;
			if(dis[v][0] + dis[i][1] + w == dis[a[1]][0]){
				sdj[i].push_back(v);
			}
		}
	}
	for(ll i = 0 ; i < n ; i++){
		o.push_back({dis[i][0] , i});
	}
	sort(all(o));
	for(ll e = 0 ; e < n ; e++){
		ll v = o[e].second;
		dp[v][0] = dis[v][2];
		dp[v][1] = dis[v][3];
		for(auto i : sdj[v]){
			dp[v][0] = min(dp[v][0] , dp[i][0]);
			dp[v][1] = min(dp[v][1] , dp[i][1]);
		}
		ans = min(ans , min(dp[v][0] + dis[v][3] , dp[v][1] + dis[v][2]));
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 440 ms 34584 KB Output is correct
2 Correct 402 ms 34364 KB Output is correct
3 Correct 415 ms 35748 KB Output is correct
4 Correct 454 ms 34672 KB Output is correct
5 Correct 422 ms 34852 KB Output is correct
6 Correct 421 ms 34620 KB Output is correct
7 Correct 462 ms 35308 KB Output is correct
8 Correct 413 ms 35068 KB Output is correct
9 Correct 401 ms 34692 KB Output is correct
10 Correct 355 ms 35064 KB Output is correct
11 Correct 166 ms 27456 KB Output is correct
12 Correct 398 ms 34652 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 34440 KB Output is correct
2 Correct 409 ms 34212 KB Output is correct
3 Correct 455 ms 34012 KB Output is correct
4 Correct 402 ms 34208 KB Output is correct
5 Correct 440 ms 34332 KB Output is correct
6 Correct 419 ms 35508 KB Output is correct
7 Correct 444 ms 35260 KB Output is correct
8 Correct 416 ms 34392 KB Output is correct
9 Correct 443 ms 34336 KB Output is correct
10 Correct 412 ms 34084 KB Output is correct
11 Correct 175 ms 28220 KB Output is correct
12 Correct 401 ms 35620 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 17996 KB Output is correct
2 Correct 9 ms 16076 KB Output is correct
3 Correct 9 ms 16076 KB Output is correct
4 Correct 38 ms 19840 KB Output is correct
5 Correct 18 ms 17764 KB Output is correct
6 Correct 10 ms 16076 KB Output is correct
7 Correct 11 ms 16172 KB Output is correct
8 Correct 11 ms 16256 KB Output is correct
9 Correct 10 ms 16076 KB Output is correct
10 Correct 19 ms 18136 KB Output is correct
11 Correct 9 ms 15948 KB Output is correct
12 Correct 9 ms 15948 KB Output is correct
13 Correct 10 ms 15956 KB Output is correct
14 Correct 10 ms 16112 KB Output is correct
15 Correct 10 ms 16076 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 440 ms 34584 KB Output is correct
2 Correct 402 ms 34364 KB Output is correct
3 Correct 415 ms 35748 KB Output is correct
4 Correct 454 ms 34672 KB Output is correct
5 Correct 422 ms 34852 KB Output is correct
6 Correct 421 ms 34620 KB Output is correct
7 Correct 462 ms 35308 KB Output is correct
8 Correct 413 ms 35068 KB Output is correct
9 Correct 401 ms 34692 KB Output is correct
10 Correct 355 ms 35064 KB Output is correct
11 Correct 166 ms 27456 KB Output is correct
12 Correct 398 ms 34652 KB Output is correct
13 Correct 405 ms 34440 KB Output is correct
14 Correct 409 ms 34212 KB Output is correct
15 Correct 455 ms 34012 KB Output is correct
16 Correct 402 ms 34208 KB Output is correct
17 Correct 440 ms 34332 KB Output is correct
18 Correct 419 ms 35508 KB Output is correct
19 Correct 444 ms 35260 KB Output is correct
20 Correct 416 ms 34392 KB Output is correct
21 Correct 443 ms 34336 KB Output is correct
22 Correct 412 ms 34084 KB Output is correct
23 Correct 175 ms 28220 KB Output is correct
24 Correct 401 ms 35620 KB Output is correct
25 Correct 23 ms 17996 KB Output is correct
26 Correct 9 ms 16076 KB Output is correct
27 Correct 9 ms 16076 KB Output is correct
28 Correct 38 ms 19840 KB Output is correct
29 Correct 18 ms 17764 KB Output is correct
30 Correct 10 ms 16076 KB Output is correct
31 Correct 11 ms 16172 KB Output is correct
32 Correct 11 ms 16256 KB Output is correct
33 Correct 10 ms 16076 KB Output is correct
34 Correct 19 ms 18136 KB Output is correct
35 Correct 9 ms 15948 KB Output is correct
36 Correct 9 ms 15948 KB Output is correct
37 Correct 10 ms 15956 KB Output is correct
38 Correct 10 ms 16112 KB Output is correct
39 Correct 10 ms 16076 KB Output is correct
40 Correct 366 ms 34464 KB Output is correct
41 Correct 382 ms 34624 KB Output is correct
42 Correct 391 ms 34736 KB Output is correct
43 Correct 201 ms 29352 KB Output is correct
44 Correct 210 ms 29428 KB Output is correct
45 Correct 481 ms 36920 KB Output is correct
46 Correct 551 ms 36476 KB Output is correct
47 Correct 408 ms 34816 KB Output is correct
48 Correct 204 ms 28804 KB Output is correct
49 Correct 460 ms 34352 KB Output is correct
50 Correct 441 ms 35944 KB Output is correct
51 Correct 493 ms 36764 KB Output is correct