Submission #683030

#TimeUsernameProblemLanguageResultExecution timeMemory
683030bebraCities (BOI16_cities)C++17
74 / 100
6102 ms173676 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define dbg(x) cerr << #x << ": " << x << endl; const int MAX_N = 1e5 + 5; const int MAX_M = 2e5 + 5; const int MAX_K = 5; const ll INF = 1e18; vector<pair<int, int>> g[MAX_N]; int vertices[MAX_K]; ll dist[MAX_K][MAX_N]; bool used[MAX_K][MAX_N]; ll dp[MAX_N][1 << MAX_K]; bool used_dp[MAX_N][1 << MAX_K]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k, m; cin >> n >> k >> m; for (int i = 0; i < k; ++i) { cin >> vertices[i]; --vertices[i]; } for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u, --v; int w; cin >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } for (int i = 0; i < k; ++i) { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.emplace(0, vertices[i]); fill_n(dist[i], n, INF); dist[i][vertices[i]] = 0; while (!pq.empty()) { auto [curr_dist, v] = pq.top(); pq.pop(); used[i][v] = true; for (const auto& [u, w] : g[v]) { if (used[i][u]) continue; if (curr_dist + w >= dist[i][u]) continue; dist[i][u] = curr_dist + w; pq.emplace(dist[i][u], u); } } } ll ans = INF; const int max_mask = (1 << k) - 1; for (int i = 0; i < k; ++i) { for (int j = 0; j < n; ++j) { for (int mask = 0; mask <= max_mask; ++mask) { dp[j][mask] = INF; used_dp[j][mask] = false; } } priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq; for (int mask = 0; mask <= max_mask; ++mask) { if (!(mask & (1 << i))) continue; dp[vertices[i]][mask] = 0; for (int j = 0; j < k; ++j) { if (mask & (1 << j)) { dp[vertices[i]][mask] += dist[j][vertices[i]]; } } pq.emplace(dp[vertices[i]][mask], vertices[i], mask); } while (!pq.empty()) { auto [curr_value, v, curr_mask] = pq.top(); if (curr_mask == max_mask) { ans = min(ans, curr_value); } pq.pop(); if (used_dp[v][curr_mask]) continue; used_dp[v][curr_mask] = true; for (const auto& [u, w] : g[v]) { for (int new_mask = curr_mask; new_mask <= max_mask; new_mask = (new_mask + 1) | curr_mask) { if (used_dp[u][new_mask]) continue; ll curr_cost = w; for (int j = 0; j < k; ++j) { if ((new_mask ^ curr_mask) & (1 << j)) { curr_cost += dist[j][u]; } } if (curr_value + curr_cost >= dp[u][new_mask]) continue; dp[u][new_mask] = curr_value + curr_cost; pq.emplace(dp[u][new_mask], u, new_mask); } } } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...