oj.uz

Submission #391053

# Submission time Handle Problem Language Result Execution time Memory
391053 2021-04-17T16:51:24 Z kostia244 Cities (BOI16_cities) C++17
100 / 100
 2676 ms 46232 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
const ll inf = 1ll<<60;
int n, k, m;
ll dp[32][maxn];
vector<array<int, 2>> g[maxn];
ll z[maxn];
void fix_layer(int msk) {
	priority_queue<pair<ll, int>> pq;
	for(int i = 1; i <= n; i++) if((z[i] = dp[msk][i]) < inf)
		pq.push({-dp[msk][i], i});
	while(!pq.empty()) {
		auto [di, v] = pq.top();
		pq.pop();di *= -1;
		//cout << di << " _ " << v << endl;
		if(z[v] < di) continue;
		for(auto [x, y] : g[v]) {
			if(z[x] > di+y) {
				z[x] = di+y;
				pq.push({-(di+y), x});
			}
		}
	}
	for(int i = 1; i <= n; i++) dp[msk][i] = z[i];
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k >> m;
	for(int j = 32; j--;)
		for(int i = 1; i <= n; i++)
			dp[j][i] = inf;
	for(int t, i = k; i--;) {
		cin >> t;
		dp[(1<<i)][t] = 0;
	}
	for(int f, t, c, i = 0; i < m; i++) {
		cin >> f >> t >> c;
		g[f].push_back({t, c});
		g[t].push_back({f, c});
	}
	for(int msk = 0; msk < 32; msk++) {
		for(int j = msk; j; j = msk&(j-1))
			for(int v = 1; v <= n; v++)
				dp[msk][v] = min(dp[msk][v], dp[msk^j][v] + dp[j][v]);
		fix_layer(msk);
	}
	ll ans = inf;
	for(int i = 1; i <= n; i++)
		ans = min(ans, dp[(1<<k)-1][i]);
	cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3532 KB Output is correct
2 Correct 3 ms 3532 KB Output is correct
3 Correct 3 ms 3532 KB Output is correct
4 Correct 3 ms 3536 KB Output is correct
5 Correct 3 ms 3532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 46148 KB Output is correct
2 Correct 619 ms 46148 KB Output is correct
3 Correct 349 ms 38348 KB Output is correct
4 Correct 71 ms 11976 KB Output is correct
5 Correct 339 ms 44016 KB Output is correct
6 Correct 66 ms 11896 KB Output is correct
7 Correct 6 ms 3936 KB Output is correct
8 Correct 4 ms 3936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3916 KB Output is correct
2 Correct 8 ms 3916 KB Output is correct
3 Correct 6 ms 3916 KB Output is correct
4 Correct 6 ms 3812 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 46200 KB Output is correct
2 Correct 1196 ms 46196 KB Output is correct
3 Correct 877 ms 38192 KB Output is correct
4 Correct 710 ms 29920 KB Output is correct
5 Correct 213 ms 15592 KB Output is correct
6 Correct 91 ms 13548 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2645 ms 46128 KB Output is correct
2 Correct 2676 ms 46232 KB Output is correct
3 Correct 2673 ms 46068 KB Output is correct
4 Correct 1744 ms 38196 KB Output is correct
5 Correct 1381 ms 29912 KB Output is correct
6 Correct 283 ms 15632 KB Output is correct
7 Correct 93 ms 13484 KB Output is correct