제출 #1128279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128279		Alihan_8	Cities (BOI16_cities)	C++20	100 / 100	2635 ms	44508 KiB

cities

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 inf = 1e15;

signed main(){
	int n, k, m; cin >> n >> k >> m;
	
	vector <vector<array<int,2>>> adj(n);
	
	vector <vector<i64>> dp(n, vector <i64> (1 << k, inf));
	
	for ( int i = 0; i < k; i++ ){
		int x; cin >> x;
		
		dp[x - 1][1 << i] = 0;
	}
	
	for ( int i = 0; i < m; i++ ){
		int u, v, w; cin >> u >> v >> w;
		
		--u, --v;
		
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	
	for ( int i = 0; i < n; i++ ) dp[i][0] = 0;
	
	for ( int mask = 0; mask < (1 << k); mask++ ){
		for ( int u = 0; u < n; u++ ){
			for ( int s = mask; s > 0; s = (s - 1) & mask ){
				dp[u][mask] = min(dp[u][mask], dp[u][s] + dp[u][mask ^ s]);
			}
		}
		
		priority_queue <array<i64,2>> q;
		
		for ( int u = 0; u < n; u++ ){
			q.push({-dp[u][mask], u});
		}
		
		while ( !q.empty() ){
			auto [val, u] = q.top();
			q.pop(); val *= -1;
			
			if ( dp[u][mask] != val ) continue;
			
			for ( auto &[v, w]: adj[u] ){
				if ( dp[v][mask] > val + w ){
					dp[v][mask] = val + w;
					q.push({-dp[v][mask], v});
				}
			}
		}
	}
	
	i64 opt = inf;
	
	for ( int u = 0; u < n; u++ ){
		opt = min(opt, dp[u][(1 << k) - 1]);
	}
	
	cout << opt << '\n';
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26