oj.uz

Submission #485524

# Submission time Handle Problem Language Result Execution time Memory
485524 2021-11-08T04:05:16 Z minhcool Cities (BOI16_cities) C++17
14 / 100
 1863 ms 54032 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);
			}
		}
	}/*
	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
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 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 53988 KB Output is correct
2 Correct 471 ms 53460 KB Output is correct
3 Correct 250 ms 41208 KB Output is correct
4 Correct 93 ms 22564 KB Output is correct
5 Correct 279 ms 53972 KB Output is correct
6 Correct 82 ms 22596 KB Output is correct
7 Correct 3 ms 3148 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3148 KB Output is correct
2 Incorrect 5 ms 3148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 863 ms 54032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1863 ms 53972 KB Output isn't correct
2 Halted 0 ms 0 KB -