oj.uz

Submission #1075413

# Submission time Handle Problem Language Result Execution time Memory
1075413 2024-08-26T05:44:08 Z Tozzyyyy Cities (BOI16_cities) C++17
100 / 100
 1287 ms 42188 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long , long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
using namespace std;

const long long inf = 1e18+1; 
const int mod = 998244353; 
const int MAXN = 1e5+100;

#define int long long
int dp[64][MAXN];
vector<pll> adj[MAXN];
int32_t main(){
  	//freopen("PAINT.INP", "r", stdin);
	//freopen("PAINT.OUT", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n , k , m; cin >> n >> k >> m;
	vector<int> a(k+1);
	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++){
		int x , y , w; cin >> x >> y >> w;
		adj[x].push_back({y , w});
		adj[y].push_back({x , w});
	}
	struct cmp{
		bool operator() (const pll &a , const pll &b) const {
			return a.se > b.se;
		}
	};
	priority_queue<pll , vector<pll> , cmp> Q;
	for(int msk = 1 ; msk < (1 << k) ; msk++){
		for(int s = (msk - 1) & msk ; s >= 1 ; 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() > 0){
			pll t = Q.top(); Q.pop();
			int u = t.fi , c = t.se;
			if(c > dp[msk][u]) continue;
			for(auto [v , w] : adj[u]){
				if(w + c < dp[msk][v]){
					dp[msk][v] = c + w;
					Q.push({v , dp[msk][v]});
				}
			}
		}

	}

	int ans = inf;
	for(int i =1  ; i <= n ; i++) ans = min(ans , dp[(1 << k) - 1][i]);
	cout << ans << "\n";

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2908 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 328 ms 23500 KB Output is correct
2 Correct 331 ms 22592 KB Output is correct
3 Correct 202 ms 16332 KB Output is correct
4 Correct 39 ms 11856 KB Output is correct
5 Correct 184 ms 20428 KB Output is correct
6 Correct 42 ms 11628 KB Output is correct
7 Correct 3 ms 2908 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 4 ms 3188 KB Output is correct
2 Correct 4 ms 3188 KB Output is correct
3 Correct 3 ms 2908 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 29724 KB Output is correct
2 Correct 615 ms 28980 KB Output is correct
3 Correct 411 ms 22608 KB Output is correct
4 Correct 374 ms 21708 KB Output is correct
5 Correct 100 ms 14008 KB Output is correct
6 Correct 45 ms 14224 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 42188 KB Output is correct
2 Correct 1287 ms 42188 KB Output is correct
3 Correct 1213 ms 41408 KB Output is correct
4 Correct 793 ms 35280 KB Output is correct
5 Correct 661 ms 28032 KB Output is correct
6 Correct 151 ms 15540 KB Output is correct
7 Correct 51 ms 14420 KB Output is correct