제출 #314085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
314085		shivensinha4	Cities (BOI16_cities)	C++17	100 / 100	5879 ms	115252 KiB

cities

#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 = 1 << x;
			if (cost[p][bm|temp] > d+dist[x][p]) {
				cost[p][bm|temp] = d+dist[x][p];
				pq.push({cost[p][bm|temp], {p, bm|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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26