oj.uz

답안 #522036

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522036 2022-02-03T16:02:56 Z blue Cities (BOI16_cities) C++17
100 / 100
 3289 ms 39596 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19028 KB Output is correct
2 Correct 13 ms 19020 KB Output is correct
3 Correct 12 ms 19116 KB Output is correct
4 Correct 12 ms 19020 KB Output is correct
5 Correct 13 ms 19020 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 720 ms 39592 KB Output is correct
2 Correct 713 ms 38836 KB Output is correct
3 Correct 359 ms 32672 KB Output is correct
4 Correct 98 ms 31320 KB Output is correct
5 Correct 310 ms 39492 KB Output is correct
6 Correct 86 ms 31432 KB Output is correct
7 Correct 15 ms 19240 KB Output is correct
8 Correct 13 ms 19268 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19284 KB Output is correct
2 Correct 19 ms 19260 KB Output is correct
3 Correct 15 ms 19256 KB Output is correct
4 Correct 15 ms 19276 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1541 ms 39596 KB Output is correct
2 Correct 1392 ms 38808 KB Output is correct
3 Correct 838 ms 32676 KB Output is correct
4 Correct 799 ms 36144 KB Output is correct
5 Correct 190 ms 31884 KB Output is correct
6 Correct 91 ms 33500 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3119 ms 39588 KB Output is correct
2 Correct 3289 ms 39592 KB Output is correct
3 Correct 3250 ms 38780 KB Output is correct
4 Correct 1642 ms 32676 KB Output is correct
5 Correct 1801 ms 36092 KB Output is correct
6 Correct 304 ms 32060 KB Output is correct
7 Correct 117 ms 33944 KB Output is correct