Submission #1306157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306157		tinhnopro2	Cities (BOI16_cities)	C++20	100 / 100	1860 ms	45452 KiB

cities

#include <bits/stdc++.h>

using namespace std;

using Node = pair<long long, int>;

const int MAXN = 2e5 + 5;
const long long INF = (long long)1e18 + 11;


int n, k, m;
vector<pair<int, int> > g[MAXN];
int special[MAXN];
long long dist[MAXN][(1 << 5) + 6];

void solve(void) {
	cin >> n >> k >> m;

	for (int i = 1; i <= k; ++i) {
		cin >> special[i];
	}

	for (int i = 1; i <= m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		g[u].push_back({v, c});
		g[v].push_back({u, c});
	}

	for (int mask = 1; mask < (1 << k); ++mask) {
		for (int u = 1; u <= n; ++u) {
			dist[u][mask] = INF;
		}

		int cnt = __builtin_popcount(mask);
		if (cnt == 1) {
			int s = special[__builtin_ctz(mask) + 1];
			dist[s][mask] = 0;
		} else {
			for (int u = 1; u <= n; ++u) {
				for (int sub = (mask - 1) & mask; sub; sub = (sub - 1) & mask) {
					for (pair<int, int> x : g[u]) {
						int v = x.first;
						int w = x.second;

						dist[u][mask] = min(dist[u][mask], dist[u][mask ^ sub] + dist[v][sub] + w);
					}
				}
			}
		}
		priority_queue<Node, vector<Node>, greater<Node> > pq;
		for (int u = 1; u <= n; ++u) pq.push({dist[u][mask], u});

		while (!pq.empty()) {
			long long dist_u = pq.top().first;
			int u = pq.top().second;

			pq.pop();

			if (dist_u > dist[u][mask]) continue;

			for (pair<int, int> x : g[u]) {
				int v = x.first;
				int w = x.second;

				if (dist[v][mask] > dist[u][mask] + w) {
					dist[v][mask] = dist[u][mask] + w;
					pq.push({dist[v][mask], v});
				}
			}
		}
	}

	long long res = INF;

	for (int u = 1; u <= n; ++u) res = min(res, dist[u][(1 << k) - 1]);

	cout << res;
}

int32_t main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

#define TASK "cau4"
	if (fopen(TASK ".inp", "r")) {
		freopen(TASK ".inp", "r", stdin);
		freopen(TASK ".out", "w", stdout);
	}

	int numTests = 1;
//	cin >> numTests;
	while (numTests--) {
		solve();
	}

	return 0;
}

// kakuai - zzz

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:87:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |                 freopen(TASK ".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:88:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |                 freopen(TASK ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26