oj.uz

Submission #394888

# Submission time Handle Problem Language Result Execution time Memory
394888 2021-04-27T12:23:22 Z wind_reaper Cities (BOI16_cities) C++17
100 / 100
 2447 ms 46820 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100000;
const int MXK = 5;
const int64_t INF = 1e16;

vector<pair<int, int64_t>> g[MXN];
int64_t dis[MXN], dp[1 << MXK][MXN];

int N, K;

void dijkstra(int mask){
	priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;

	for(int v = 0; v < N; v++){
		dis[v] = dp[mask][v];
		pq.emplace(dp[mask][v], v);
	}

	while(!pq.empty()){
		auto [d, u] = pq.top();
		pq.pop();

		if(d != dis[u])
			continue;

		for(auto& [v, di] : g[u]){
			if(dis[v] > dis[u] + di){
				dis[v] = dis[u] + di;
				pq.emplace(dis[v], v);
			}
		}
	}

	for(int v = 0; v < N; v++)
		dp[mask][v] = dis[v];
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int M;

	cin >> N >> K >> M;

	vector<int> imp(K);
	for(auto& v : imp){
		cin >> v;
		--v;
	}

	for(int mask = 0; mask < (1 << K); mask++)
		for(int v = 0; v < N; v++)
			dp[mask][v] = INF;

	for(int i = 0; i < M; i++){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}

	for(int i = 0; i < K; i++)
		dp[1 << i][imp[i]] = 0;

	for(int mask = 1; mask < (1 << K); mask++){
		for(int smask = mask; smask; smask = (smask-1)&mask)
			for(int v = 0; v < N; v++)
				dp[mask][v] = min(dp[mask][v], dp[smask][v] + dp[smask^mask][v]);

		dijkstra(mask);
	}

	int64_t ans = INF;

	for(int v = 0; v < N; v++)
		ans = min(ans, dp[(1 << K)-1][v]);

	cout << ans << '\n';

	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 27976 KB Output is correct
2 Correct 617 ms 27344 KB Output is correct
3 Correct 411 ms 19992 KB Output is correct
4 Correct 79 ms 13100 KB Output is correct
5 Correct 367 ms 24744 KB Output is correct
6 Correct 76 ms 13032 KB Output is correct
7 Correct 5 ms 2892 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1402 ms 34124 KB Output is correct
2 Correct 1278 ms 33744 KB Output is correct
3 Correct 822 ms 26108 KB Output is correct
4 Correct 690 ms 24920 KB Output is correct
5 Correct 207 ms 15932 KB Output is correct
6 Correct 82 ms 15528 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2446 ms 46820 KB Output is correct
2 Correct 2440 ms 46688 KB Output is correct
3 Correct 2447 ms 46200 KB Output is correct
4 Correct 1625 ms 38800 KB Output is correct
5 Correct 1259 ms 31264 KB Output is correct
6 Correct 330 ms 17292 KB Output is correct
7 Correct 97 ms 15820 KB Output is correct