oj.uz

Submission #670942

# Submission time Handle Problem Language Result Execution time Memory
670942 2022-12-11T12:41:29 Z dozer Cities (BOI16_cities) C++14
74 / 100
 6000 ms 241560 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 69084 KB Output is correct
2 Correct 860 ms 68368 KB Output is correct
3 Correct 385 ms 45520 KB Output is correct
4 Correct 80 ms 13520 KB Output is correct
5 Correct 386 ms 50552 KB Output is correct
6 Correct 59 ms 12600 KB Output is correct
7 Correct 5 ms 3412 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4048 KB Output is correct
2 Correct 10 ms 4004 KB Output is correct
3 Correct 6 ms 3284 KB Output is correct
4 Correct 8 ms 3784 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2725 ms 142932 KB Output is correct
2 Correct 2554 ms 142332 KB Output is correct
3 Correct 1358 ms 64004 KB Output is correct
4 Correct 1710 ms 78476 KB Output is correct
5 Correct 387 ms 39388 KB Output is correct
6 Correct 119 ms 17160 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6053 ms 241560 KB Time limit exceeded
2 Halted 0 ms 0 KB -