Submission #1075413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075413		Tozzyyyy	Cities (BOI16_cities)	C++17	100 / 100	1287 ms	42188 KiB

cities

//#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26