oj.uz

Submission #1075354

# Submission time Handle Problem Language Result Execution time Memory
1075354 2024-08-26T03:52:00 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1266 ms 46276 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, KM = 5, inf = 1e18;

int n, k, m, f[KM+5];
vector <pii> adj[NM+5];
int d[(1<<KM)+5][NM+5];
priority_queue <pii, vector <pii>, greater <pii> > pq;
int ans = +inf;

void solve(){
	for (int msk = 1; msk < (1<<k); msk++){
		for (int i = 1; i <= n; i++) d[msk][i] = +inf;
		if (__builtin_popcount(msk) == 1) d[msk][f[__lg(msk)]] = 0;
		while (!pq.empty()) pq.pop();
		for (int i = 1; i <= n; i++){
			for (int j = (msk-1)&msk; j > 0; j = (j-1)&msk){
				d[msk][i] = min(d[msk][i], d[j][i]+d[msk-j][i]);
			}
			pq.push(mp(d[msk][i], i));
		}
		while (!pq.empty()){
			if (d[msk][pq.top().se] != pq.top().fi){
				pq.pop();
				continue;
			}
			int u = pq.top().se; pq.pop();
			for (pii _ : adj[u]){
				int v = _.fi, c = _.se;
				if (d[msk][u]+c < d[msk][v]){
					d[msk][v] = d[msk][u]+c;
					pq.push(mp(d[msk][v], v));
				}
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> k >> m;
	for (int i = 0; i < k; i++)
		cin >> f[i];
	while (m--){
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back(mp(v, c));
		adj[v].push_back(mp(u, c));
	}
	solve();
	for (int i = 1; i <= n; i++)
		ans = min(ans, d[(1<<k)-1][i]);
	cout << ans;
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 3 ms 23388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 27068 KB Output is correct
2 Correct 313 ms 26684 KB Output is correct
3 Correct 192 ms 17856 KB Output is correct
4 Correct 47 ms 21332 KB Output is correct
5 Correct 179 ms 24772 KB Output is correct
6 Correct 41 ms 19196 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 6 ms 15168 KB Output is correct
3 Correct 4 ms 15196 KB Output is correct
4 Correct 4 ms 15196 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 32408 KB Output is correct
2 Correct 596 ms 32036 KB Output is correct
3 Correct 391 ms 26152 KB Output is correct
4 Correct 354 ms 31420 KB Output is correct
5 Correct 109 ms 28692 KB Output is correct
6 Correct 47 ms 29776 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 46012 KB Output is correct
2 Correct 1266 ms 46276 KB Output is correct
3 Correct 1199 ms 44720 KB Output is correct
4 Correct 825 ms 36780 KB Output is correct
5 Correct 689 ms 41660 KB Output is correct
6 Correct 166 ms 37316 KB Output is correct
7 Correct 58 ms 38228 KB Output is correct