# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
392888 |
2021-04-22T07:17:59 Z |
arujbansal |
Cities (BOI16_cities) |
C++17 |
|
2546 ms |
49660 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>
using namespace std;
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long
const int MXN = 1e5 + 5, INF = 1e18;
int N, M, K;
vector<pair<int, int>> g[MXN];
vector<int> important;
int dp[(1 << 5)][MXN], dist[MXN];
void run_dijkstra(int mask) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int v = 0; v < N; v++) {
pq.emplace(dp[mask][v], v);
dist[v] = dp[mask][v];
}
while (!pq.empty()) {
auto [cur_dist, u] = pq.top();
pq.pop();
if (cur_dist != dist[u]) continue;
for (const auto &[v, w] : g[u]) {
int new_dist = cur_dist + w;
if (new_dist < dist[v]) {
dist[v] = new_dist;
pq.emplace(new_dist, v);
}
}
}
for (int v = 0; v < N; v++)
dp[mask][v] = dist[v];
}
void solve() {
cin >> N >> K >> M;
important.resize(K);
for (auto &x : important) {
cin >> x;
x--;
}
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
for (int i = 0; i < (1 << K); i++)
for (int j = 0; j < N; j++)
dp[i][j] = INF;
for (int i = 0; i < K; i++)
dp[1 << i][important[i]] = 0;
for (int mask = 0; mask < (1 << K); mask++) {
for (int v = 0; v < N; v++)
for (int submask = mask; submask > 0; submask = (submask - 1) & mask)
dp[mask][v] = min(dp[mask][v], dp[submask][v] + dp[mask ^ submask][v]);
run_dijkstra(mask);
}
int ans = INF;
for (int v = 0; v < N; v++)
ans = min(ans, dp[(1 << K) - 1][v]);
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int TC = 1;
// cin >> TC;
while (TC--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2764 KB |
Output is correct |
5 |
Correct |
2 ms |
2764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
652 ms |
26532 KB |
Output is correct |
2 |
Correct |
633 ms |
30360 KB |
Output is correct |
3 |
Correct |
391 ms |
20808 KB |
Output is correct |
4 |
Correct |
78 ms |
15272 KB |
Output is correct |
5 |
Correct |
389 ms |
27640 KB |
Output is correct |
6 |
Correct |
70 ms |
15172 KB |
Output is correct |
7 |
Correct |
5 ms |
2984 KB |
Output is correct |
8 |
Correct |
4 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3056 KB |
Output is correct |
2 |
Correct |
7 ms |
3092 KB |
Output is correct |
3 |
Correct |
6 ms |
2892 KB |
Output is correct |
4 |
Correct |
5 ms |
3024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1268 ms |
33120 KB |
Output is correct |
2 |
Correct |
1270 ms |
36684 KB |
Output is correct |
3 |
Correct |
760 ms |
26968 KB |
Output is correct |
4 |
Correct |
687 ms |
27752 KB |
Output is correct |
5 |
Correct |
190 ms |
18416 KB |
Output is correct |
6 |
Correct |
81 ms |
17616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2469 ms |
45552 KB |
Output is correct |
2 |
Correct |
2546 ms |
49660 KB |
Output is correct |
3 |
Correct |
2484 ms |
49220 KB |
Output is correct |
4 |
Correct |
1569 ms |
39552 KB |
Output is correct |
5 |
Correct |
1246 ms |
34252 KB |
Output is correct |
6 |
Correct |
284 ms |
19836 KB |
Output is correct |
7 |
Correct |
94 ms |
17976 KB |
Output is correct |