oj.uz

Submission #258102

# Submission time Handle Problem Language Result Execution time Memory
258102 2020-08-05T11:07:29 Z maximath_1 Cities (BOI16_cities) C++11
100 / 100
 1254 ms 28200 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
#define ll long long
const ll inf = 1e18 + 69;

int n, k, m;
vector<pair<int, int> > adj[100005];
ll dp[16][100005];
bitset<100005> vis;
int imp[5], rt;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k >> m;
	cin >> rt; k --;
	for(int i = 0; i < k; i ++) cin >> imp[i];
	for(int u, v, w, i = 0; i < m; i ++){
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	for(int i = 0; i < 16; i ++) for(int j = 1; j <= n; j ++){
		if(i == 0) dp[i][j] = 0;
		else dp[i][j] = inf;
	}

	for(int msk = 0; msk < (1 << k); msk ++){
		priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
		for(int i = 1; i <= n; i ++){
			for(int submsk = (msk - 1) & msk; submsk; submsk = (submsk - 1) & msk)
				dp[msk][i] = min(dp[msk][i], dp[submsk][i] + dp[submsk ^ msk][i]);
			vis[i] = 0;
			pq.push({dp[msk][i], i});
		}

		for(; !pq.empty();){
			int nw = pq.top().second; pq.pop();
			if(vis[nw]) continue;
			vis[nw] = 1;
			for(auto i : adj[nw]){
				int nx = i.first, wt = i.second;
				if(dp[msk][nx] > dp[msk][nw] + wt){
					dp[msk][nx] = dp[msk][nw] + wt;
					pq.push({dp[msk][nx], nx});
				}
			}
		}

		for(int i = 0; i < k; i ++)
			dp[msk | (1 << i)][imp[i]] = min(dp[msk | (1 << i)][imp[i]], dp[msk][imp[i]]);
	}

	cout << dp[(1 << k) - 1][rt] << endl;
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 28120 KB Output is correct
2 Correct 405 ms 28076 KB Output is correct
3 Correct 208 ms 22004 KB Output is correct
4 Correct 92 ms 7584 KB Output is correct
5 Correct 256 ms 27880 KB Output is correct
6 Correct 75 ms 7544 KB Output is correct
7 Correct 4 ms 3072 KB Output is correct
8 Correct 3 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB Output is correct
2 Correct 5 ms 3072 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 4 ms 2944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 27972 KB Output is correct
2 Correct 681 ms 28100 KB Output is correct
3 Correct 449 ms 22004 KB Output is correct
4 Correct 399 ms 18496 KB Output is correct
5 Correct 128 ms 10432 KB Output is correct
6 Correct 86 ms 9264 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 28200 KB Output is correct
2 Correct 1222 ms 28168 KB Output is correct
3 Correct 1159 ms 27984 KB Output is correct
4 Correct 914 ms 22288 KB Output is correct
5 Correct 678 ms 18568 KB Output is correct
6 Correct 173 ms 10428 KB Output is correct
7 Correct 86 ms 9140 KB Output is correct