oj.uz

Submission #392127

# Submission time Handle Problem Language Result Execution time Memory
392127 2021-04-20T14:22:48 Z soroush Cities (BOI16_cities) C++17
100 / 100
 2990 ms 48184 KB 
//曇り空 のぞいた予感
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , k , m;
ll red[10], dist[5][maxn];
vector < pii > adj[maxn];
ll ans = 1e18;
priority_queue < pii > pq;
bool mark[maxn];

void djk(int v , ll *dist){
	for(int i = 1 ; i <= n ; i ++)dist[i] = 1e17;
	dist[v] = 0;
	pq.push({-dist[v] , v});
	ms(mark  , 0);
	while(pq.size()){
		int v = pq.top().second;
		pq.pop();
		if(mark[v])continue;
		mark[v] = 1;
		for(auto u : adj[v])if(dist[u.first] > dist[v] + u.second){
			dist[u.first] = dist[v] + u.second;
			pq.push(pii(-dist[u.first] , u.first));
		}
	}
}

ll d[maxn][32];

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> k >> m;
	for(int i = 0 ; i < k ; i ++)
		cin >> red[i];
	for(int i = 1 ; i <= m ; i ++){
		int u , v , w;
		cin >> u >> v >> w;
		adj[u].pb({v , w});
		adj[v].pb({u , w});
	}
	for(int i = 0 ; i < k ; i ++)
		djk(red[i] , dist[i]);	
	for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j < (1 << k) ; j ++)d[i][j] = 1e17;
	for(int i = 1 ; i <= n ; i ++)for(int j = 0 ; j < k ; j ++)d[i][(1 << j)] = dist[j][i];
	for(int j = 1 ; j < (1 << k) ; j ++){
		for(int i = 1 ; i <= n ; i ++){
			for(int k = 1 ; k < j ; k ++)if((j & k) == k){
				d[i][j] = min(d[i][j] , d[i][k] + d[i][j^k]);
			}
			pq.push({-d[i][j] , i});
		}
		ms(mark , 0);
		while(pq.size()){
			int v = pq.top().second;
			pq.pop();
			if(mark[v])continue;
			mark[v] = 1;
			for(auto u : adj[v])if(d[u.first][j] > d[v][j] + u.second){
				d[u.first][j] = d[v][j] + u.second;
				pq.push(pii(-d[u.first][j] , u.first));
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++)ans = min(ans , d[i][(1 << k) - 1]);
	cout << ans;
	return(0);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 2 ms 2764 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 45816 KB Output is correct
2 Correct 775 ms 44332 KB Output is correct
3 Correct 480 ms 39608 KB Output is correct
4 Correct 83 ms 15428 KB Output is correct
5 Correct 441 ms 48184 KB Output is correct
6 Correct 75 ms 15492 KB Output is correct
7 Correct 5 ms 3212 KB Output is correct
8 Correct 4 ms 3148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3276 KB Output is correct
2 Correct 7 ms 3208 KB Output is correct
3 Correct 6 ms 3148 KB Output is correct
4 Correct 5 ms 3020 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 46700 KB Output is correct
2 Correct 1471 ms 47344 KB Output is correct
3 Correct 983 ms 40504 KB Output is correct
4 Correct 835 ms 33708 KB Output is correct
5 Correct 209 ms 18932 KB Output is correct
6 Correct 86 ms 17648 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2953 ms 47296 KB Output is correct
2 Correct 2990 ms 47316 KB Output is correct
3 Correct 2816 ms 48040 KB Output is correct
4 Correct 1922 ms 41248 KB Output is correct
5 Correct 1550 ms 34144 KB Output is correct
6 Correct 308 ms 19108 KB Output is correct
7 Correct 102 ms 17836 KB Output is correct