Submission #670942

#	Time	Username	Problem	Language	Result	Execution time	Memory
670942		dozer	Cities (BOI16_cities)	C++14	74 / 100	6053 ms	241560 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define M 40
#define int long long
 
int arr[N], dist[N][M], flag[N];
vector<pii> adj[N];
 
const int INF = 1e18 + 7;
 
int32_t main()
{
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();
 
 	int n, m, k;
 	cin>>n>>k>>m;
 	for (int i = 1; i <= k; i++)
 	{
 		int node;
 		cin>>node;
 		flag[node] = 1;
 		arr[node] = i - 1;
 	}
 
 	for (int i = 1; i <= m; i++)
 	{
 		int u, v, w;
 		cin>>u>>v>>w;
 		adj[u].pb({v, w});
 		adj[v].pb({u, w});
 	}
 
 	for (int i = 1; i <= n; i++) for (int j = 0; j < (1<<k); j++) dist[i][j] = INF;
 
 	priority_queue<array<int, 3>> q;
 	for (int i = 1; i <= n; i++)
 	{
 		if (flag[i]) q.push({0, i, (1<<arr[i])}), dist[i][(1<<arr[i])] = 0;
 	}
 
 	while(!q.empty())
 	{
 		array<int, 3> tmp = q.top();
 		q.pop();
 		int top = tmp[1], mask = tmp[2], d = -tmp[0];
 		if (d != dist[top][mask]) continue;
 		int comp = ((1<<k) - 1) ^ mask;
 		for (auto i : adj[top])
 		{
 			int v = i.st, w = i.nd;
 			for (int j = comp; j > 0; j = (j - 1) & comp)
 			{
 				int gh = mask | j;
 				if (dist[v][gh] > w + d + dist[v][j])
 				{
 					dist[v][gh] = w + d + dist[v][j];
 					q.push({-dist[v][gh], v, gh});
 				}
 			}
 			int gh = mask;
 			if (dist[v][gh] > w + d)
			{
				dist[v][gh] = w + d;
				q.push({-dist[v][gh], v, gh});
			}
 		}
 	}
 
 	int ans = INF;
 	for (int i = 1; i <= n; i++)
 	{
 		//cout<<i<<sp<<dist[i][(1<<k) - 1]<<endl;
 		ans = min(ans, dist[i][(1<<k) - 1]);
 	}
 	cout<<ans<<endl;
 
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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