oj.uz

Submission #826404

# Submission time Handle Problem Language Result Execution time Memory
826404 2023-08-15T14:28:28 Z serifefedartar Cities (BOI16_cities) C++17
100 / 100
 1612 ms 48904 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<vector<pair<int,ll>>> graph;
vector<int> imp;
ll dp[32][MAXN];
int main() {
	fast
	int n, k, m;
	cin >> n >> k >> m;

	graph = vector<vector<pair<int,ll>>>(n, vector<pair<int,ll>>());
	for (int i = 0; i < k; i++) {
		int node; cin >> node;
		node--;
		imp.push_back(node);
	}

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

	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < MAXN; j++)
			dp[i][j] = 1e15;
	}
	for (int i = 0; i < k; i++) {
		dp[(1<<i)][imp[i]] = 0;
	}

	const int mx_mask = (1<<k) - 1;
	for (int mask = 0; mask <= mx_mask; mask++) {
		for (int comp = 0; comp <= mask; comp++) {
			if ((comp & mask) != comp)
				continue;
			for (int node = 0; node < n; node++)
				dp[mask][node] = min(dp[mask][node], dp[comp][node] + dp[mask ^ comp][node]);
		}

		priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
		for (int node = 0; node < n; node++) {
			if (dp[mask][node] != 1e15)
				pq.push({dp[mask][node], node});
		}

		vector<int> vis(n, false);
		while (!pq.empty()) {
			ll dist = pq.top().f;
			int node = pq.top().s;
			pq.pop();

			if (vis[node])
				continue;
			vis[node] = true;
			for (auto u : graph[node]) {
				ll nDist = u.s;
				int to = u.f;
				if (dist + nDist < dp[mask][to]) {
					dp[mask][to] = dist + nDist;
					pq.push({dp[mask][to], to});
				}
			}
		}
	}

	ll ans = 1e15;
	for (int i = 0; i < n; i++)
		ans = min(ans, dp[mx_mask][i]);
	cout << ans << "\n";
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25288 KB Output is correct
2 Correct 11 ms 25292 KB Output is correct
3 Correct 11 ms 25332 KB Output is correct
4 Correct 11 ms 25292 KB Output is correct
5 Correct 11 ms 25288 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 48712 KB Output is correct
2 Correct 391 ms 48232 KB Output is correct
3 Correct 196 ms 38688 KB Output is correct
4 Correct 56 ms 37868 KB Output is correct
5 Correct 223 ms 48560 KB Output is correct
6 Correct 53 ms 37904 KB Output is correct
7 Correct 11 ms 25560 KB Output is correct
8 Correct 11 ms 25556 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25548 KB Output is correct
2 Correct 13 ms 25604 KB Output is correct
3 Correct 12 ms 25432 KB Output is correct
4 Correct 12 ms 25556 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 48796 KB Output is correct
2 Correct 725 ms 48224 KB Output is correct
3 Correct 484 ms 38736 KB Output is correct
4 Correct 436 ms 44860 KB Output is correct
5 Correct 126 ms 39308 KB Output is correct
6 Correct 58 ms 40160 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1612 ms 48904 KB Output is correct
2 Correct 1599 ms 48800 KB Output is correct
3 Correct 1596 ms 48232 KB Output is correct
4 Correct 994 ms 38908 KB Output is correct
5 Correct 858 ms 44808 KB Output is correct
6 Correct 191 ms 39396 KB Output is correct
7 Correct 67 ms 40228 KB Output is correct