Submission #852951

#TimeUsernameProblemLanguageResultExecution timeMemory
852951wakandaaaCities (BOI16_cities)C++17
100 / 100
2293 ms49764 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define file "" #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define getbit(x, i) (((x) >> (i)) & 1) #define bit(x) (1LL << (x)) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e5 + 5; const int mod = (int)1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int oo = 1e9; const long long ooo = 1e18; template<class X, class Y> bool mini(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maxi(X &a, Y b) { return a < b ? (a = b, true) : false; } void add(int &a, int b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int n, m, k; vector<pair<int, int> > adj[N]; int d[N][1 << 5]; vector<int> node; bool vis[N]; signed main() { ios::sync_with_stdio(false); cin.tie(0); // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); cin >> n >> k >> m; node.resize(k); for (int i = 0; i < k; ++i) { cin >> node[i]; --node[i]; } for (int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; --u; --v; adj[u].emplace_back(v, c); adj[v].emplace_back(u, c); } memset(d, 0x3f, sizeof d); long long INF = d[0][0]; for (int i = 0; i < k; ++i) { d[node[i]][1 << i] = 0; } for (int mask = 1; mask < bit(k); ++mask) { for (int x = mask; x; x = (x - 1) & mask) { int y = mask ^ x; for (int u = 0; u < n; ++u) { mini(d[u][mask], d[u][x] + d[u][y]); } } memset(vis, 0, sizeof vis); typedef pair<long long, int> node; priority_queue<node, vector<node>, greater<node> > q; for (int u = 0; u < n; ++u) { if (d[u][mask] == INF) continue; q.emplace(d[u][mask], u); } while (q.size()) { long long du; int u; tie(du, u) = q.top(); q.pop(); if (vis[u]) continue; vis[u] = true; for (auto [v, c] : adj[u]) { if (mini(d[v][mask], du + c)) q.emplace(d[v][mask], v); } } } long long res = INF; for (int u = 0; u < n; ++u) mini(res, d[u][bit(k) - 1]); cout << res; 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...