oj.uz

Submission #675104

# Submission time Handle Problem Language Result Execution time Memory
675104 2022-12-27T01:58:11 Z thiago_bastos Cities (BOI16_cities) C++17
100 / 100
 3245 ms 92872 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

const int N = 2e5 + 10, K = 5;
int n, m, k, city[K];
vector<ii> adj[N];
i64 cost[N][1 << K];
bool vis[N][1 << K];

void solve() {

	cin >> n >> k >> m;

	for(int i = 0; i < k; ++i) {
		cin >> city[i];
		--city[i];
	}

	for(int i = 0; i < n; ++i)
		for(int j = 0; j < (1 << k); ++j)
			cost[i][j] = INFLL;	

	for(int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}

	for(int i = 0; i < k; ++i) cost[city[i]][1<<i] = 0;

	for(int i = 1; i < k; ++i) {
		priority_queue<tuple<i64, int, int>> pq;

		for(int v = 0; v < n; ++v) {
			for(int j = 0; j < (1 << k); ++j) {
				if(__builtin_popcount(j) != i) continue;
				pq.emplace(-cost[v][j], v, j);		
			}
		}

		while(!pq.empty()) {
			auto [c, v, mask] = pq.top(); pq.pop();
			if(vis[v][mask]) continue;
			vis[v][mask] = true;		
			for(auto [u, w] : adj[v]) {
				i64 C = -c + w;
				if(C >= cost[u][mask]) continue;
				cost[u][mask] = C;
				pq.emplace(-C, u, mask);
			}
		}

		for(int v = 0; v < n; ++v) {
			for(int j = 0; j < (1 << k); ++j) {
				if(__builtin_popcount(j) != i + 1) continue;
				for(int S = j; S; S = (S - 1) & j)
					cost[v][j] = min(cost[v][j], cost[v][S] + cost[v][S ^ j]);
			}
		}
	}

	i64 best = INFLL;
	for(int v = 0; v < n; ++v) best = min(best, cost[v][(1<<k)-1]);
	cout << best << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 57784 KB Output is correct
2 Correct 623 ms 57420 KB Output is correct
3 Correct 398 ms 51352 KB Output is correct
4 Correct 60 ms 13848 KB Output is correct
5 Correct 292 ms 52060 KB Output is correct
6 Correct 64 ms 13600 KB Output is correct
7 Correct 6 ms 5588 KB Output is correct
8 Correct 4 ms 5420 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5648 KB Output is correct
2 Correct 9 ms 5624 KB Output is correct
3 Correct 6 ms 5588 KB Output is correct
4 Correct 6 ms 5332 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 72204 KB Output is correct
2 Correct 1522 ms 73968 KB Output is correct
3 Correct 927 ms 63016 KB Output is correct
4 Correct 786 ms 43828 KB Output is correct
5 Correct 177 ms 20548 KB Output is correct
6 Correct 66 ms 15496 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3018 ms 92872 KB Output is correct
2 Correct 3086 ms 92872 KB Output is correct
3 Correct 3245 ms 92420 KB Output is correct
4 Correct 2306 ms 70496 KB Output is correct
5 Correct 1807 ms 55648 KB Output is correct
6 Correct 324 ms 22664 KB Output is correct
7 Correct 86 ms 15496 KB Output is correct