oj.uz

Submission #314087

# Submission time Handle Problem Language Result Execution time Memory
314087 2020-10-18T09:15:30 Z shivensinha4 Cities (BOI16_cities) C++17
100 / 100
 5896 ms 111176 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXK = 5, MXN = 2e5;
const ll INF = 1e15;
int n, k, m;
vi terminals;
ll dist[MXK+1][MXN+1];
vector<pair<int, ll>> adj[MXN+1];

void calcDist() {
	for_(i, 0, k) {
		for_(j, 0, n) dist[i][j] = INF;
		dist[i][terminals[i]] = 0;
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
		pq.push({0, terminals[i]});
		while (pq.size()) {
			int p = pq.top().second;
			ll d = pq.top().first; pq.pop();
			if (d > dist[i][p]) continue;
			for (auto j: adj[p]) if (dist[i][j.first] > d+j.second) {
				dist[i][j.first] = d+j.second;
				pq.push({dist[i][j.first], j.first});
			}
		}
	}
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k >> m;
	terminals.resize(k);
	for_(i, 0, k) {
		cin >> terminals[i];
		terminals[i] -= 1;
	}
	
	for_(i, 0, m) {
		int a, b; ll d; cin >> a >> b >> d;
		a -= 1; b -= 1;
		adj[a].push_back({b, d}); adj[b].push_back({a, d});
	}
	
	calcDist();
	
	ll ans = INF;
	int till = (1 << k);
	ll cost[n+1][till+1];
	priority_queue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> pq;
	
	for_(i, 0, n) {
		for_(x, 1, till) cost[i][x] = INF;
		pq.push({0, {i, 0}});
	}
	
	while (pq.size()) {
		int p = pq.top().second.first, bm = pq.top().second.second;
		ll d = pq.top().first; pq.pop();
		if (d > cost[p][bm]) continue;
		if (bm == till-1) ans = min(ans, d);
		for_(x, 0, k) {
			int temp = bm | (1 << x);
			if (cost[p][temp] > d+dist[x][p]) {
				cost[p][temp] = d+dist[x][p];
				pq.push({cost[p][temp], {p, temp}});
			}
		}
		for (auto j: adj[p]) if (cost[j.first][bm] > d+j.second) {
			cost[j.first][bm] = d+j.second;
			pq.push({cost[j.first][bm], {j.first, bm}});
		}
	}
	
	cout << ans << endl;
	
	

	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 33256 KB Output is correct
2 Correct 1063 ms 32304 KB Output is correct
3 Correct 682 ms 28000 KB Output is correct
4 Correct 96 ms 14256 KB Output is correct
5 Correct 532 ms 25116 KB Output is correct
6 Correct 79 ms 14008 KB Output is correct
7 Correct 8 ms 5400 KB Output is correct
8 Correct 6 ms 5376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5760 KB Output is correct
2 Correct 11 ms 5760 KB Output is correct
3 Correct 9 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2641 ms 64960 KB Output is correct
2 Correct 2313 ms 63968 KB Output is correct
3 Correct 1819 ms 43344 KB Output is correct
4 Correct 1375 ms 40232 KB Output is correct
5 Correct 284 ms 19832 KB Output is correct
6 Correct 94 ms 16760 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5806 ms 111176 KB Output is correct
2 Correct 5896 ms 110968 KB Output is correct
3 Correct 5283 ms 110160 KB Output is correct
4 Correct 4018 ms 106024 KB Output is correct
5 Correct 3054 ms 63296 KB Output is correct
6 Correct 545 ms 25316 KB Output is correct
7 Correct 117 ms 16756 KB Output is correct