oj.uz

Submission #258324

# Submission time Handle Problem Language Result Execution time Memory
258324 2020-08-05T18:06:58 Z Berted Cities (BOI16_cities) C++14
100 / 100
 1315 ms 32496 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define pii pair<ll, int>
#define fst first
#define snd second
#define vpi vector<pii>
#define ppi pair<ll, pii>

const ll INF = 1e16;

using namespace std;

priority_queue<pii> pq;
int n, k, m, spc[6];
ll dst[1 << 4][100001];
vpi adj[100001];
ll res = INF;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	for (int i = 0; i < k; i++) {cin >> spc[i]; spc[i]--;}
	k--;
	for (int i = 0; i < m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		adj[u - 1].push_back({w, v - 1});
		adj[v - 1].push_back({w, u - 1});
	}
	for (int i = 0; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++) {dst[i][j] = INF;}
	}
	for (int i = 0; i < k; i++) {dst[1 << i][spc[i]] = 0;}
	for (int i = 1; i < (1 << k); i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int s = i; s; s = (s - 1) & i)
			{
				dst[i][j] = min(dst[i][j], dst[s][j] + dst[i ^ s][j]);
			}
			pq.push({-dst[i][j], j});
		}
		while (pq.size())
		{
			int u = pq.top().snd; ll d = -pq.top().fst; pq.pop();
			if (dst[i][u] == d)
			{
				for (auto v : adj[u])
				{
					if (dst[i][u] + v.fst < dst[i][v.snd])
					{
						dst[i][v.snd] = dst[i][u] + v.fst;
						pq.push({-dst[i][v.snd], v.snd});
					}
				}
			}
		}
	}
	cout << dst[(1 << k) - 1][spc[k]] << "\n";
	return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 23144 KB Output is correct
2 Correct 452 ms 22248 KB Output is correct
3 Correct 191 ms 15388 KB Output is correct
4 Correct 77 ms 14392 KB Output is correct
5 Correct 231 ms 21484 KB Output is correct
6 Correct 78 ms 14328 KB Output is correct
7 Correct 4 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 26220 KB Output is correct
2 Correct 761 ms 25304 KB Output is correct
3 Correct 489 ms 18540 KB Output is correct
4 Correct 409 ms 21100 KB Output is correct
5 Correct 164 ms 16216 KB Output is correct
6 Correct 89 ms 16760 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 32496 KB Output is correct
2 Correct 1244 ms 32492 KB Output is correct
3 Correct 1315 ms 31632 KB Output is correct
4 Correct 754 ms 24812 KB Output is correct
5 Correct 631 ms 24428 KB Output is correct
6 Correct 186 ms 16856 KB Output is correct
7 Correct 87 ms 16632 KB Output is correct