Submission #377143

#	Time	Username	Problem	Language	Result	Execution time	Memory
377143		pavement	Cities (BOI16_cities)	C++17	100 / 100	2561 ms	42464 KiB

cities

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, K, M, A[15], dp[1 << 5][100005];
vector<ii> adj[100005];
priority_queue<ii, vector<ii>, greater<ii> > pq;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K >> M;
	for (int i = 1; i <= K; i++) cin >> A[i];
	for (int i = 1, u, v, w; i <= M; i++) {
		cin >> u >> v >> w;
		adj[u].eb(v, w);
		adj[v].eb(u, w);
	}
	for (int i = 0; i < (1 << K); i++)
		for (int j = 1; j <= N; j++) dp[i][j] = 1e17;
	for (int i = 1; i <= K; i++) dp[1 << (i - 1)][A[i]] = 0;
	for (int i = 1; i < (1 << K); i++) {
		for (int j = i; j; j = (j - 1) & i)
			for (int k = 1; k <= N; k++)
				dp[i][k] = min(dp[i][k], dp[j][k] + dp[i ^ j][k]);
		for (int k = 1; k <= N; k++)
			pq.emplace(dp[i][k], k);
		while (!pq.empty()) {
			auto curr = pq.top();
			pq.pop();
			if (dp[i][curr.second] != curr.first) continue;
			for (auto u : adj[curr.second])
				if (curr.first + u.second < dp[i][u.first]) {
					dp[i][u.first] = curr.first + u.second;
					pq.emplace(dp[i][u.first], u.first);
				}
		}
	}
	cout << dp[(1 << K) - 1][A[1]] << '\n';
}

Compilation message (stderr)

cities.cpp:32:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main() {
      |      ^

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