oj.uz

Submission #485525

# Submission time Handle Problem Language Result Execution time Memory
485525 2021-11-08T04:07:01 Z minhcool Cities (BOI16_cities) C++17
100 / 100
 4074 ms 54056 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, m, k;
 
int dp[N][32], nodes[N];
 
vector<ii> Adj[N];
 
vector<iii> edge;
 
void dijik(int msk){
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	for(int i = 1; i <= n; i++) pq.push({dp[i][msk], i});
	//return;
	//int itr = 0;
	while(!pq.empty()){
		//itr++;
		int u = pq.top().se, d = pq.top().fi;
		//cout << u << "\n";
		//if(itr == 1) return;
		pq.pop();
		if(d != dp[u][msk]) continue;
		for(auto it : Adj[u]){
			int v = it.fi, w = it.se;
			if(dp[v][msk] <= dp[u][msk] + w) continue;
			dp[v][msk] = dp[u][msk] + w;
			pq.push({dp[v][msk], v});
		}
	}
}
 
void process(){
	cin >> n >> k >> m;
	for(int i = 0; i < k; i++) cin >> nodes[i];
	for(int i = 1; i <= m; i++){
		int x, y, w;
		cin >> x >> y >> w;
		Adj[x].pb({y, w});
		Adj[y].pb({x, w});
		edge.pb({{x, y}, w});
		edge.pb({{y, x}, w});
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1ll << k); j++) dp[i][j] = oo;
	}
	for(int i = 0; i < k; i++){
		//for(int j = 1; j <= n; j++) dp[j][(1LL << i)] = oo;
		dp[nodes[i]][1LL << i] = 0;
		dijik(1LL << i);
	}
	//return;
	for(int i = 0; i < (1LL << k); i++){
		if(__builtin_popcountll(i) <= 1) continue;
		for(int sub = i - 1; sub; sub = (sub - 1) & i){
			for(auto it : edge){
				dp[it.fi.fi][i] = min(dp[it.fi.fi][i], dp[it.fi.fi][sub] + dp[it.fi.se][i ^ sub] + it.se);
			}
		}
      dijik(i);
	}/*
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (1ll << k); j++) cout << i << " " << j << " " << dp[i][j] << "\n";
	}*/
	int mn = oo;
	for(int i = 1; i <= n; i++) mn = min(mn, dp[i][(1LL << k) - 1]);
	cout << mn;
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 53968 KB Output is correct
2 Correct 739 ms 53420 KB Output is correct
3 Correct 456 ms 41288 KB Output is correct
4 Correct 100 ms 22660 KB Output is correct
5 Correct 353 ms 53976 KB Output is correct
6 Correct 71 ms 22576 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 4 ms 3212 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3204 KB Output is correct
2 Correct 7 ms 3196 KB Output is correct
3 Correct 5 ms 3020 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 1784 ms 53972 KB Output is correct
2 Correct 1763 ms 53392 KB Output is correct
3 Correct 1040 ms 41180 KB Output is correct
4 Correct 1089 ms 38740 KB Output is correct
5 Correct 271 ms 25248 KB Output is correct
6 Correct 169 ms 23740 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3894 ms 53964 KB Output is correct
2 Correct 4074 ms 54056 KB Output is correct
3 Correct 3998 ms 53464 KB Output is correct
4 Correct 2464 ms 41184 KB Output is correct
5 Correct 2522 ms 38740 KB Output is correct
6 Correct 643 ms 25324 KB Output is correct
7 Correct 404 ms 23508 KB Output is correct