oj.uz

Submission #394784

# Submission time Handle Problem Language Result Execution time Memory
394784 2021-04-27T10:11:08 Z Nima_Naderi Cities (BOI16_cities) C++14
100 / 100
 2667 ms 54596 KB 
//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 1e5 + 10;
const ll MXK = 5;
const ll MXM = (1LL << 5) + 5;
const ll INF = 1e18;
ll n, m, k, ans;
ll Imp[MXK], dis[MXK][MXN], dp[MXM][MXN];
vector<pll> adj[MXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;
bool vis[MXN], in[MXN];
void BFS(ll f, ll src){
	dis[f][src] = 0, pq.push({0, src});
	memset(vis, 0, sizeof vis);
	while(!pq.empty()){
		ll d, u; tie(d, u) = pq.top(); pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto Pr : adj[u]){
			ll v, w; tie(v, w) = Pr;
			if(!vis[v] && d + w < dis[f][v]){
				dis[f][v] = d + w;
				pq.push({dis[f][v], v});
			}
		}
	}
}
void Relax(ll f){
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i ++) pq.push({dp[f][i], i});
	while(!pq.empty()){
		ll d, u; tie(d, u) = pq.top(); pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto Pr : adj[u]){
			ll v, w; tie(v, w) = Pr;
			if(!vis[v] && d + w < dp[f][v]){
				dp[f][v] = d + w;
				pq.push({dp[f][v], v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	memset(dis, 63, sizeof dis), memset(dp, 63, sizeof dp);
	for(int i = 0; i < k; i ++) cin >> Imp[i];
	for(int i = 0; i < m; i ++){
		ll u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for(int i = 0; i < k; i ++) BFS(i, Imp[i]);
	for(int i = 0; i < k; i ++) dp[(1LL << i)][Imp[i]] = 0;
	for(int mask = 1; mask < (1LL << k); mask ++){
		for(int i = 1; i <= n; i ++){
			for(int sub = mask; sub; sub = (sub - 1) & mask){
				int oth = mask ^ sub;
				dp[mask][i] = min(dp[mask][i], dp[sub][i] + dp[oth][i]);
			}
		}
		Relax(mask);
	}
	cout << *min_element(dp[(1LL << k) - 1] + 1, dp[(1LL << k) - 1] + n + 1) << '\n';
	return 0;
}
//! N.N

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35532 KB Output is correct
2 Correct 19 ms 35632 KB Output is correct
3 Correct 19 ms 35524 KB Output is correct
4 Correct 19 ms 35580 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 54400 KB Output is correct
2 Correct 803 ms 53572 KB Output is correct
3 Correct 425 ms 45112 KB Output is correct
4 Correct 111 ms 48068 KB Output is correct
5 Correct 460 ms 54448 KB Output is correct
6 Correct 101 ms 48084 KB Output is correct
7 Correct 22 ms 35756 KB Output is correct
8 Correct 22 ms 35844 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 35836 KB Output is correct
2 Correct 25 ms 35772 KB Output is correct
3 Correct 24 ms 35660 KB Output is correct
4 Correct 23 ms 35840 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 54596 KB Output is correct
2 Correct 1394 ms 53528 KB Output is correct
3 Correct 872 ms 45112 KB Output is correct
4 Correct 787 ms 52532 KB Output is correct
5 Correct 233 ms 49572 KB Output is correct
6 Correct 129 ms 50432 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2667 ms 54492 KB Output is correct
2 Correct 2642 ms 54324 KB Output is correct
3 Correct 2556 ms 53516 KB Output is correct
4 Correct 1588 ms 45112 KB Output is correct
5 Correct 1365 ms 52532 KB Output is correct
6 Correct 352 ms 49576 KB Output is correct
7 Correct 165 ms 50568 KB Output is correct