oj.uz

Submission #1075432

# Submission time Handle Problem Language Result Execution time Memory
1075432 2024-08-26T06:01:06 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1299 ms 46536 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll dp[70][N];
vector<pll>adj[N];
ll a[N];
ll n,k,m;
void to_thic_cau(){ 
	cin >> n >> k >> m;
	for(int i = 0; i < (1 << k);i++){
		for(int j = 1; j <= n;j++) dp[i][j] = inf;
	}
	for(int i = 1; i <= k;i++){
		cin >> a[i];
		dp[1 << (i - 1)][a[i]] = 0;
	}
	for(int i = 1; i <= m;i++){
		ll u,v,c; cin >> u >> v >> c;
		adj[u].pb({v, c}); adj[v].pb({u, c});
	}
	struct cmp{
		bool operator()(const pll &a, const pll &b){
			return a.S > b.S;
		}
	};
	priority_queue<pll, vector<pll>, cmp>q;
	for(int msk = 1; msk < (1 << k);msk++){
		for(int s = (msk - 1) & msk; s > 0; s = (s - 1) & msk){
			for(int i = 1; i <= n;i++){
				dp[msk][i] = min(dp[s][i] + dp[msk ^ s][i], dp[msk][i]);
			}
		}
		for(int i = 1; i <= n;i++) q.push({i, dp[msk][i]});
		while(q.size()){
			ll u = q.top().F, c = q.top().S; q.pop();
			if(c > dp[msk][u]) continue;
			for(auto x : adj[u]){
				ll v = x.F, w = x.S;
				if(dp[msk][u] + w < dp[msk][v]){
					dp[msk][v] = dp[msk][u] + w;
					q.push({v, dp[msk][v]});
				}
			}
		}
	}
	ll res = inf;
	for(int i = 1; i <= n;i++){
		res = min(res, dp[(1 << k) - 1][i]);
	}
	cout<< res << '\n';
}     

signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll tc = 1;
	// cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2828 KB Output is correct
4 Correct 1 ms 2828 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 27844 KB Output is correct
2 Correct 309 ms 26776 KB Output is correct
3 Correct 202 ms 18628 KB Output is correct
4 Correct 42 ms 15248 KB Output is correct
5 Correct 166 ms 24524 KB Output is correct
6 Correct 40 ms 15184 KB Output is correct
7 Correct 3 ms 2904 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3164 KB Output is correct
2 Correct 4 ms 3164 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 3 ms 3056 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 33912 KB Output is correct
2 Correct 623 ms 33228 KB Output is correct
3 Correct 426 ms 24776 KB Output is correct
4 Correct 381 ms 26056 KB Output is correct
5 Correct 98 ms 17840 KB Output is correct
6 Correct 46 ms 17544 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1268 ms 46452 KB Output is correct
2 Correct 1299 ms 46536 KB Output is correct
3 Correct 1208 ms 45752 KB Output is correct
4 Correct 865 ms 37316 KB Output is correct
5 Correct 671 ms 32188 KB Output is correct
6 Correct 147 ms 19384 KB Output is correct
7 Correct 54 ms 18000 KB Output is correct