oj.uz

Submission #1075422

# Submission time Handle Problem Language Result Execution time Memory
1075422 2024-08-26T05:55:03 Z vjudge1 Cities (BOI16_cities) C++17
0 / 100
 454 ms 52112 KB 
#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 = 5e5 + 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({u, dp[msk][u]});
				}
			}
		}
	}
	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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12120 KB Output is correct
2 Correct 5 ms 12120 KB Output is correct
3 Incorrect 5 ms 12212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 33292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 39632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 454 ms 52112 KB Output isn't correct
2 Halted 0 ms 0 KB -