Submission #522036

#	Time	Username	Problem	Language	Result	Execution time	Memory
522036		blue	Cities (BOI16_cities)	C++17	100 / 100	3289 ms	39596 KiB

cities

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int mxn = 100'000;
const int mxk = 5;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;

const ll INF = 1'000'000'000'000'000'000LL;

vvll dp(mxn, vll(1 << (mxk-1), INF));
vector<pll> edge[mxn];

int n, k, m;

vi special(mxk);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k >> m;

	for(int j = 0; j < k; j++)
	{
		cin >> special[j];
		special[j]--;
	}
	// cerr << "read\n";

	for(int e = 0; e < m; e++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;

		edge[a].push_back({b, c});
		edge[b].push_back({a, c});
	}


	for(int i = 0; i < n; i++)
	{
		dp[i][0] = 0;
	}

	vvi subsets((1 << (k-1)));
	for(int m1 = 0; m1 < (1 << (k-1)); m1++)	
		for(int m2 = m1; m2 < (1 << (k-1)); m2++)
			if((m1 & m2) == m1)
				subsets[m2].push_back(m1);

	for(int mask = 1; mask < (1 << (k-1)); mask++)
	{
		for(int j = 0; j < (k-1); j++)
		{
			if((1 << j) == mask)
				dp[special[j]][mask] = 0;
		}

		for(int mask2: subsets[mask])
		{
			for(int i = 0; i < n; i++)
			{
				dp[i][mask] = min(dp[i][mask], dp[i][mask2] + dp[i][mask ^ mask2]);
			}
		}

		set<pll> tbv;
		for(int i = 0; i < n; i++)
			tbv.insert({dp[i][mask], i});

		while(!tbv.empty())
		{
			int u = tbv.begin()->second;
			tbv.erase(tbv.begin());

			for(auto ed: edge[u])
			{
				int v = ed.first;
				ll w = ed.second;

				if(dp[v][mask] <= dp[u][mask] + w) continue;

				tbv.erase({dp[v][mask], v});
				dp[v][mask] = dp[u][mask] + w;
				tbv.insert({dp[v][mask], v});
			}
		}


		// for(int i = 0; i < n; i++)
		// {
		// 	cerr << "s = " << i << " | m = ";
		// 	for(int v = 0; v < k-1; v++)
		// 	{
		// 		if(mask & (1 << v)) cerr << special[v] << ' ';
		// 	}
		// 	cerr << " : " << dp[i][mask] << '\n';
		// }
	}

	cout << dp[ special[k-1] ][(1 << (k-1)) - 1] << '\n';
}

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