oj.uz

답안 #314090

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314090 2020-10-18T09:24:57 Z shivensinha4 Cities (BOI16_cities) C++17
100 / 100
 5627 ms 111180 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'

class Compare {
public:
	bool operator() (pair<ll, ii> a, pair<ll, ii> b) {
		return a.first > b.first;
	}
};

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>>, Compare> pq;
	
	for_(i, 0, n) for_(x, 0, till) cost[i][x] = INF;
	
	for_(i, 0, k) {
		int temp = 1 << i;
		cost[terminals[i]][temp] = 0;
		pq.push({0, {terminals[i], temp}});
	}
	
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1110 ms 33104 KB Output is correct
2 Correct 1047 ms 32268 KB Output is correct
3 Correct 556 ms 24164 KB Output is correct
4 Correct 84 ms 14528 KB Output is correct
5 Correct 523 ms 25136 KB Output is correct
6 Correct 77 ms 14188 KB Output is correct
7 Correct 7 ms 5504 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5760 KB Output is correct
2 Correct 12 ms 5760 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2544 ms 64808 KB Output is correct
2 Correct 2263 ms 63956 KB Output is correct
3 Correct 1594 ms 43344 KB Output is correct
4 Correct 1398 ms 40292 KB Output is correct
5 Correct 317 ms 23904 KB Output is correct
6 Correct 98 ms 17140 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5555 ms 111180 KB Output is correct
2 Correct 5627 ms 110920 KB Output is correct
3 Correct 5082 ms 110180 KB Output is correct
4 Correct 3652 ms 105936 KB Output is correct
5 Correct 3047 ms 63296 KB Output is correct
6 Correct 587 ms 25236 KB Output is correct
7 Correct 119 ms 17264 KB Output is correct