Submission #392127

#	Time	Username	Problem	Language	Result	Execution time	Memory
392127		soroush	Cities (BOI16_cities)	C++17	100 / 100	2990 ms	48184 KiB

cities

//曇り空 のぞいた予感
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , k , m;
ll red[10], dist[5][maxn];
vector < pii > adj[maxn];
ll ans = 1e18;
priority_queue < pii > pq;
bool mark[maxn];

void djk(int v , ll *dist){
	for(int i = 1 ; i <= n ; i ++)dist[i] = 1e17;
	dist[v] = 0;
	pq.push({-dist[v] , v});
	ms(mark  , 0);
	while(pq.size()){
		int v = pq.top().second;
		pq.pop();
		if(mark[v])continue;
		mark[v] = 1;
		for(auto u : adj[v])if(dist[u.first] > dist[v] + u.second){
			dist[u.first] = dist[v] + u.second;
			pq.push(pii(-dist[u.first] , u.first));
		}
	}
}

ll d[maxn][32];

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> k >> m;
	for(int i = 0 ; i < k ; i ++)
		cin >> red[i];
	for(int i = 1 ; i <= m ; i ++){
		int u , v , w;
		cin >> u >> v >> w;
		adj[u].pb({v , w});
		adj[v].pb({u , w});
	}
	for(int i = 0 ; i < k ; i ++)
		djk(red[i] , dist[i]);	
	for(int i = 1 ; i <= n ; i ++)for(int j = 1 ; j < (1 << k) ; j ++)d[i][j] = 1e17;
	for(int i = 1 ; i <= n ; i ++)for(int j = 0 ; j < k ; j ++)d[i][(1 << j)] = dist[j][i];
	for(int j = 1 ; j < (1 << k) ; j ++){
		for(int i = 1 ; i <= n ; i ++){
			for(int k = 1 ; k < j ; k ++)if((j & k) == k){
				d[i][j] = min(d[i][j] , d[i][k] + d[i][j^k]);
			}
			pq.push({-d[i][j] , i});
		}
		ms(mark , 0);
		while(pq.size()){
			int v = pq.top().second;
			pq.pop();
			if(mark[v])continue;
			mark[v] = 1;
			for(auto u : adj[v])if(d[u.first][j] > d[v][j] + u.second){
				d[u.first][j] = d[v][j] + u.second;
				pq.push(pii(-d[u.first][j] , u.first));
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++)ans = min(ans , d[i][(1 << k) - 1]);
	cout << ans;
	return(0);
}

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