Submission #1105507

#TimeUsernameProblemLanguageResultExecution timeMemory
1105507_callmelucianCities (BOI16_cities)C++14
100 / 100
5513 ms171416 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<ll,int,int> tpl; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 1e5 + 5; vector<pii> adj[mn]; ll dist[mn][1 << 5], gather[mn]; bool vis[mn][1 << 5]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, m; cin >> n >> k >> m; for (int i = 1; i <= n; i++) for (int mask = 1; mask < (1 << k); mask++) dist[i][mask] = LLONG_MAX; priority_queue<tpl> pq; vector<int> fav(k); for (int i = 0; i < k; i++) { cin >> fav[i]; dist[fav[i]][1 << i] = 0; pq.emplace(0, fav[i], 1 << i); } while (m--) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } while (pq.size()) { ll d; int u, mask; tie(d, u, mask) = pq.top(); pq.pop(); if (vis[u][mask]) continue; vis[u][mask] = 1; for (pii it : adj[u]) { int v, w; tie(v, w) = it; for (int supr = mask; supr < (1 << k); supr = (supr + 1) | mask) { if (dist[v][supr ^ mask] == LLONG_MAX) continue; if (dist[u][mask] + dist[v][supr ^ mask] + w < dist[v][supr]) { dist[v][supr] = dist[u][mask] + dist[v][supr ^ mask] + w; pq.emplace(-dist[v][supr], v, supr); } } } } ll ans = LLONG_MAX; for (int i : fav) ans = min(ans, dist[i][(1 << k) - 1]); cout << ans; 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...