Submission #44953

#	Time	Username	Problem	Language	Result	Execution time	Memory
44953		MatheusLealV	Cities (BOI16_cities)	C++17	0 / 100	333 ms	44868 KiB

cities

#include <bits/stdc++.h>
#define inf 2000000000
#define N 100050
#define P 40
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

ll n, m, k, city[10], dp[P][N], id[N];

vector<pii> grafo[N];

void dijkstra()
{
	priority_queue< pair<pii, int>, vector<pair<pii, int> >, greater < pair<pii, int > > > pq;

	for(int i = 1; i <= n; i++)
		for(int j = 0; j < P; j++)
			dp[j][i] = inf;

	for(int i = 0; i < k; i++) dp[1<<i][city[i]] = 0, pq.push( { { 0, (1<<i) }, city[i] } );

	while(!pq.empty())
	{
		int x = pq.top().s, mask = pq.top().f.s, d = pq.top().f.f;
		
		pq.pop();

		if(d > dp[mask][x]) continue;

		for(auto v: grafo[x])
		{
			int mask2 = mask;

			if(id[v.f]) (mask2 |= (1<<(id[v.f])));

			if(dp[ mask2 ][v.f] > dp[mask][x] + v.s)
			{
				dp[ mask2 ][v.f] = dp[mask][x] + v.s;
			
				pq.push({{ dp[mask2][v.f], mask2 }, v.f});
			}
		}	
	}
}

ll dp2[P][P], x;

int solve(int id, int mask)
{
	if(mask == (1<<k) - 1) return 0;

	if(id >= P || mask >= P) return inf;

	if(dp2[id][mask] != -1) return dp2[id][mask];

	int mask2 = (mask | id);

	ll add = (dp[id][x] < inf ? (solve(id + 1, mask2) + dp[id][x]) : inf);

	ll nadd = solve(id + 1, mask);

	//cout<<x<<" "<<id<<" "<<mask<<" "<<add<<" "<<nadd<<"\n";

	return dp2[id][mask] = min(add, nadd);
}

/*
	for(int id = 39; id >= 0; id --)
	{
		for(int mask = 0; mask < 40; mask ++)
		{
			
		}
	}

*/

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>k>>m;

	for(int i = 0; i < k; i++) cin>>city[i], id[ city[i] ] = i;

	for(int i = 1, a, b, c; i <= m; i++)
	{
		cin>>a>>b>>c;

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

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

	dijkstra();

	memset(dp2, -1, sizeof dp2);

	int ans = inf;

	for(int i = 1; i <= n; i++)
	{
		memset(dp2, -1, sizeof dp2);

		x = i;

		ans = min(ans, solve(0, 0));
	}

	cout<<ans<<"\n";
}

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