Submission #1075432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075432		vjudge1	Cities (BOI16_cities)	C++17	100 / 100	1299 ms	46536 KiB

cities

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