제출 #314083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
314083		shivensinha4	Cities (BOI16_cities)	C++17	22 / 100	6095 ms	115304 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();
	//for_(i, 0, k) {
		//cout << terminals[i] << ": ";
		//for_(j, 0, n) cout << dist[i][j] << " ";
		//cout << endl;
	//}
	
	ll ans = INF;
	int till = (1 << k);
	for_(i, 0, n) {
		ll cost[n+1][till+1];
		for_(j, 0, n) for_(x, 0, till) cost[j][x] = INF;	
		//int idx = -1;
		//for_(j, 0, k) if (terminals[j] == i) {
			//idx = j;
			//break;
		//}
		
		//if (idx != -1) idx = 1 << idx;
		//else idx = 0;
		
		cost[i][0] = 0;
		priority_queue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> pq;
		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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26