oj.uz

답안 #670941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670941 2022-12-11T12:40:23 Z dozer Cities (BOI16_cities) C++14
74 / 100
 6000 ms 245704 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<pair<int, pii>> 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())
 	{
 		pair<int, pii> tmp = q.top();
 		q.pop();
 		int top = tmp.nd.st, mask = tmp.nd.nd, d = -tmp.st;
 		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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2684 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 908 ms 73232 KB Output is correct
2 Correct 794 ms 72648 KB Output is correct
3 Correct 366 ms 47664 KB Output is correct
4 Correct 78 ms 16876 KB Output is correct
5 Correct 372 ms 54784 KB Output is correct
6 Correct 61 ms 16140 KB Output is correct
7 Correct 5 ms 3476 KB Output is correct
8 Correct 3 ms 3272 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 4048 KB Output is correct
2 Correct 9 ms 4048 KB Output is correct
3 Correct 5 ms 3284 KB Output is correct
4 Correct 8 ms 3920 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2618 ms 147268 KB Output is correct
2 Correct 2481 ms 146532 KB Output is correct
3 Correct 1302 ms 66072 KB Output is correct
4 Correct 1780 ms 82452 KB Output is correct
5 Correct 393 ms 43212 KB Output is correct
6 Correct 125 ms 20592 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6040 ms 245704 KB Time limit exceeded
2 Halted 0 ms 0 KB -