Submission #422679

#	Time	Username	Problem	Language	Result	Execution time	Memory
422679		Maqsut_03	Cities (BOI16_cities)	C++14	0 / 100	7 ms	460 KiB

cities

#include <iostream>
#include <fstream>
#include <cmath>
#include <random>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <functional>
#include <typeinfo>

#include <vector>
#include <array>
#include <valarray>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>

#define ll long long
#define ff first
#define ss second
#define sz size()
const int M = 1e9+7, N = 50;
using namespace std;

int n, m, k, a[10];
ll ans = M, ans0 = 0, ans1;
vector<pair<ll, ll> > g[N];
bool used[N], used2[N], used3[N];

void dfs(int v, int u, ll s)
{
	used[v] = 1;
	if (v == u && ans > s)
	{
		ans = s;
		for (int i=1; i<=n; i++) used2[i] = used[i];
		return ;
	}
	for (auto [x, y]:g[v])
	{
		if (!used[x]) dfs(x, u, s + y);
	}
	used[v] = 0;
}


void dfs2(int v, int u, ll s = 0)
{
	used[v] = 1;
	
	if (v == u && ans > s)
	{
		ans = s;
		for (int i=1; i<=n; i++) used2[i] = used[i];
		return ;
	}
	
	for (auto [x, y]:g[v])
	{
		if (!used[x]) dfs(x, u, s + y);
	}
	
	used[v] = 0;
}

int main()
{
	cin >> n >> k >> m;
	for (int i=1; i<=k; i++) cin >> a[i];
	int x, y;
	ll z;
	for (int i=1; i<=m; i++)
	{
		cin >> x >> y >> z;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);	
	}
	
	dfs(a[1], a[2], 0);
	ans0 += ans;
	int k0 = 3;
	bool q0 = 1;
	while (k0 <= k)
	{
		if (q0)for (int i=1; i<=n; i++) used[i] |= used2[i];
		else for (int i=1; i<=n; i++) used[i] |= used3[i];
		q0 = 0;
		fill(used2, used2 + N, 0);
		ans1 = M;
		for (int i=1; i<=n; i++)
		{
			ans = M;
			if (used[i])
			{
				dfs2(i, a[k0]);
			}
			if (ans < ans1)
			{
				ans1 = ans;
				for (int i=1; i<=n; i++) used3[i] = used2[i];
			}
		}
		ans0+=ans1;
		k0++;
	}
	cout << ans0;
}

Compilation message (stderr)

cities.cpp: In function 'void dfs(int, int, long long int)':
cities.cpp:46:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |  for (auto [x, y]:g[v])
      |            ^
cities.cpp: In function 'void dfs2(int, int, long long int)':
cities.cpp:65:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for (auto [x, y]:g[v])
      |            ^

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