Submission #80847

#	Time	Username	Problem	Language	Result	Execution time	Memory
80847		scanhex	Cities (BOI16_cities)	C++17	100 / 100	2712 ms	99168 KiB

cities

#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
using ll = long long;
 
nagai oo = 1e18;
 
const int N = 1e5;
 
vector<pair<int, int>> g[N];
 
const int SZ = 32;
 
nagai dp[SZ][N];
 
const int MEM = 200000000;
char arr[MEM];
int ptr = 0;
void* operator new(size_t n)
{
	ptr += n;
	return (void*)(arr + ptr - n);
}
void operator delete(void*){}
 
int cur_layer = 0;
 
struct cmp
{
	bool operator()(int a, int b) const
	{
		if (dp[cur_layer][a] != dp[cur_layer][b])
			return dp[cur_layer][a] > dp[cur_layer][b];
		return a > b;
	}
};
 
priority_queue<pair<nagai, int>> st;
 
bool used[N];
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k, m;
	cin >> n >> k >> m;
	vector<int> imp(k);
	for (auto& x : imp)
		cin >> x, --x;
	for (int i = 0; i < m; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		--a, --b;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	int sz = 1 << k;
	for (int i = 0; i < sz; ++i)
		for (int j = 0; j < n; ++j)
			dp[i][j] = oo;
	for (int i = 0; i < k; ++i)
		dp[1 << i][imp[i]] = 0;
	for (int i = 1; i < sz; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			for (int k = i; k > 0; k = (k - 1) & i)
				dp[i][j] = min(dp[i][j], dp[k][j] + dp[i ^ k][j]);
		}
		cur_layer = i;
		for (int j = 0; j < n; ++j)
			st.push({-dp[i][j], j});
		fill(used, used + n, false);
		while (st.size())
		{
			 pair<nagai, int> px = st.top();
			 st.pop();
			 int x = px.second;
			 if (used[x])
				 continue;
			 used[x] = true;
			 for (auto p : g[x])
			 {
				 if (dp[i][x] + p.second < dp[i][p.first])
				 {
					  dp[i][p.first] = dp[i][x] + p.second;
					  st.push({-dp[i][p.first], p.first});
				 }
			 }
		}
	}
	cout << *min_element(dp[sz - 1], dp[sz - 1] + n) << '\n';
	return 0;
}

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