oj.uz

Submission #693842

# Submission time Handle Problem Language Result Execution time Memory
693842 2023-02-03T09:58:17 Z ajab_01 Cities (BOI16_cities) C++17
100 / 100
 3267 ms 72252 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int K = 5;
long long INF;
vector<pair<int , int> > g[N];
vector<int> vec;
long long dp[N][1 << K] , ans;
int n , k , m;
bool vis[N];

void dij(int mask , int sit){
	priority_queue<pair<long long , int> > pq;
	for(int i = 1 ; i <= n ; i++)
		if(dp[i][mask] < INF)
			pq.push({-dp[i][mask] , i});
	while(!pq.empty()){
		int ver = pq.top().second;
		pq.pop();
		if(vis[ver]) continue;
		vis[ver] = 1;
		if(sit) ans = min(ans , dp[ver][mask]);
		for(auto i : g[ver]){
			int w = i.second , v = i.first;
			if(dp[v][mask] > dp[ver][mask] + w){
				dp[v][mask] = dp[ver][mask] + w;
				pq.push({-dp[v][mask] , v});
			}
		}
	}
	for(int i = 1 ; i <= n ; i++)
		vis[i] = 0;
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> k >> m;
	for(int i = 0 ; i < k ; i++){
		int x;
		cin >> x;
		vec.push_back(x);
	}
	for(int i = 0 ; i < m ; i++){
		int u , v , w;
		cin >> u >> v >> w;
		g[u].push_back({v , w});
		g[v].push_back({u , w});
	}

	memset(dp , 63 , sizeof(dp));

	ans = INF = dp[0][0];

	for(int i = 0 ; i < k ; i++){
		dp[vec[i]][1 << i] = 0;
		dij(1 << i , 0);
	}

	for(int mask = 3 ; mask < (1 << k) ; mask++){
		int cnt = 0;
		for(int i = 0 ; i < k ; i++)
			if(mask & (1 << i))
				cnt++;
		if(cnt == 1) continue;
		for(int v = 1 ; v <= n ; v++){
			for(auto j : g[v]){
				int u = j.first , w = j.second , sub = mask;
				while(sub){
					dp[v][mask] = min(dp[v][mask] , dp[v][sub] + dp[u][mask ^ sub] + w);
					sub--;
					sub &= mask;
				}
			}
		}
		dij(mask , (mask == (1 << k) - 1 ? 1 : 0));
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 55072 KB Output is correct
2 Correct 21 ms 55036 KB Output is correct
3 Correct 22 ms 55112 KB Output is correct
4 Correct 24 ms 55088 KB Output is correct
5 Correct 21 ms 55072 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 72040 KB Output is correct
2 Correct 696 ms 72000 KB Output is correct
3 Correct 412 ms 64084 KB Output is correct
4 Correct 103 ms 63272 KB Output is correct
5 Correct 362 ms 69964 KB Output is correct
6 Correct 81 ms 63240 KB Output is correct
7 Correct 25 ms 55264 KB Output is correct
8 Correct 24 ms 55228 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 55220 KB Output is correct
2 Correct 34 ms 55212 KB Output is correct
3 Correct 30 ms 55172 KB Output is correct
4 Correct 25 ms 55188 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1525 ms 72036 KB Output is correct
2 Correct 1486 ms 71992 KB Output is correct
3 Correct 995 ms 64072 KB Output is correct
4 Correct 922 ms 68524 KB Output is correct
5 Correct 268 ms 64672 KB Output is correct
6 Correct 135 ms 64892 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3162 ms 72252 KB Output is correct
2 Correct 3267 ms 72140 KB Output is correct
3 Correct 2949 ms 72076 KB Output is correct
4 Correct 2165 ms 64192 KB Output is correct
5 Correct 1838 ms 68540 KB Output is correct
6 Correct 454 ms 64576 KB Output is correct
7 Correct 252 ms 64888 KB Output is correct