Submission #258324

#	Time	Username	Problem	Language	Result	Execution time	Memory
258324		Berted	Cities (BOI16_cities)	C++14	100 / 100	1315 ms	32496 KiB

cities

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<ll, int>
#define fst first
#define snd second
#define vpi vector<pii>
#define ppi pair<ll, pii>

const ll INF = 1e16;

using namespace std;

priority_queue<pii> pq;
int n, k, m, spc[6];
ll dst[1 << 4][100001];
vpi adj[100001];
ll res = INF;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	for (int i = 0; i < k; i++) {cin >> spc[i]; spc[i]--;}
	k--;
	for (int i = 0; i < m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		adj[u - 1].push_back({w, v - 1});
		adj[v - 1].push_back({w, u - 1});
	}
	for (int i = 0; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++) {dst[i][j] = INF;}
	}
	for (int i = 0; i < k; i++) {dst[1 << i][spc[i]] = 0;}
	for (int i = 1; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int s = i; s; s = (s - 1) & i)
			{
				dst[i][j] = min(dst[i][j], dst[s][j] + dst[i ^ s][j]);
			}
			pq.push({-dst[i][j], j});
		}
		while (pq.size())
		{
			int u = pq.top().snd; ll d = -pq.top().fst; pq.pop();
			if (dst[i][u] == d)
			{
				for (auto v : adj[u])
				{
					if (dst[i][u] + v.fst < dst[i][v.snd])
					{
						dst[i][v.snd] = dst[i][u] + v.fst;
						pq.push({-dst[i][v.snd], v.snd});
					}
				}
			}
		}
	}
	cout << dst[(1 << k) - 1][spc[k]] << "\n";
	return 0;
}

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