oj.uz

Submission #648458

# Submission time Handle Problem Language Result Execution time Memory
648458 2022-10-06T15:21:25 Z ymm Cities (BOI16_cities) C++17
100 / 100
 2105 ms 47620 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
const ll inf = 1e17;
const int K = 5;
ll dis[1<<K][N];
vector<pll> A[N];
int imp[K];
int n, k, m;

void dij(int msk)
{
	priority_queue<pll, vector<pll>, greater<pll>> s;
	int fi = __builtin_ctz(msk);
	Loop (v,0,n) {
		int submsk = msk;
		int cnt = __builtin_popcount(msk);
		Loop (_,0,1<<cnt) {
			dis[msk][v] = min(  dis[submsk][v]
			                  + dis[submsk ^ msk][v],
					  dis[msk][v]);
			submsk = (submsk - 1) & msk;
		}
		s.push({dis[msk][v], v});
	}
	while (s.size()) {
		auto [d, v] = s.top();
		s.pop();
		if (d > dis[msk][v])
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w < dis[msk][u]) {
				dis[msk][u] = d + w;
				s.push({dis[msk][u], u});
			}
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k >> m;
	Loop (i,0,k) {
		cin >> imp[i];
		--imp[i];
	}
	Loop (i,0,m) {
		ll v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	Loop (msk,1,1<<k) Loop (v,0,n)
		dis[msk][v] = inf;
	Loop (i,0,k)
		dis[1<<i][imp[i]] = 0;
	Loop (msk,1,1<<k)
		dij(msk);
	ll ans = inf;
	Loop (v,0,n)
		ans = min(ans, dis[(1<<k)-1][v]);
	cout << ans << '\n';
}

Compilation message

cities.cpp: In function 'void dij(int)':
cities.cpp:20:6: warning: unused variable 'fi' [-Wunused-variable]
   20 |  int fi = __builtin_ctz(msk);
      |      ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 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 538 ms 25020 KB Output is correct
2 Correct 488 ms 24532 KB Output is correct
3 Correct 348 ms 17024 KB Output is correct
4 Correct 58 ms 11816 KB Output is correct
5 Correct 310 ms 21996 KB Output is correct
6 Correct 59 ms 11724 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1034 ms 31404 KB Output is correct
2 Correct 1033 ms 35024 KB Output is correct
3 Correct 656 ms 25556 KB Output is correct
4 Correct 574 ms 27172 KB Output is correct
5 Correct 151 ms 18188 KB Output is correct
6 Correct 73 ms 17516 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2105 ms 43996 KB Output is correct
2 Correct 2013 ms 43800 KB Output is correct
3 Correct 2001 ms 47620 KB Output is correct
4 Correct 1410 ms 38176 KB Output is correct
5 Correct 1083 ms 33352 KB Output is correct
6 Correct 248 ms 19784 KB Output is correct
7 Correct 83 ms 17932 KB Output is correct