Submission #44951

#	Time	Username	Problem	Language	Result	Execution time	Memory
44951		MatheusLealV	Cities (BOI16_cities)	C++17	0 / 100	2 ms	392 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<int, int> pii;

int 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});
			}
		}	
	}
}

int dp2[N][P][P];

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

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

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

	int mask2 = (mask | id);

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

	int nadd = solve(x, id + 1, mask);

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

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

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++) ans = min(ans, solve(i, 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