제출 #1188972

#제출 시각아이디문제언어결과실행 시간메모리
1188972g4yuhgCities (BOI16_cities)C++20
14 / 100
6071 ms241592 KiB
#include<bits/stdc++.h> typedef long long ll; #define endl '\n' #define fi first #define se second #define pii pair<ll,ll> #define N 200005 #define LOG 19 #define inf 1e16 using namespace std; ll onbit(ll mask, ll i) { return mask | (1 << i); } ll getbit(ll mask, ll i) { return (mask >> i) & 1; } ll n, k, m, d[5][N]; ll d2[(1 << 5)][N]; ll ip[5]; vector<pii> adj[N]; void dij() { for (int i = 1; i <= n; i ++) { for (int j = 0; j < k; j ++) { d[j][i] = inf; } } priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq; for (int i = 0; i < k; i ++) { d[i][ip[i]] = 0; pq.push({0, {i, ip[i]}}); } while (pq.size()) { auto c = pq.top().fi; auto u = pq.top().se; //if (u.fi == 2) cout << c << " " << u.fi << " " << u.se << endl; pq.pop(); if (c > d[u.fi][u.se]) continue; for (auto v : adj[u.se]) { if (d[u.fi][v.fi] > c + v.se) { d[u.fi][v.fi] = c + v.se; pq.push({d[u.fi][v.fi], {u.fi, v.fi}}); } } } } void dij2() { for (int i = 1; i <= n; i ++) { for (int j = 0; j < (1 << k); j ++) { d2[j][i] = inf; } } priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq; for (int i = 1; i <= n; i ++) { for (int j = 0; j < k; j ++) { d2[(1 << j)][i] = d[j][i]; pq.push({d2[(1 << j)][i], {(1 << j), i}}); //cout << "push: " << d2[(1 << j)][i] << " " << (1 << j) << " " << i << endl; } } while (pq.size()) { auto c = pq.top().fi; auto u = pq.top().se; //if (u.fi == 7) cout << c << " " << u.fi << " " << u.se << endl; pq.pop(); if (c > d2[u.fi][u.se]) continue; for (auto v : adj[u.se]) { ll newc = c + v.se; for (int mask = 0; mask < (1 << k); mask ++) { //if ((mask & u.fi) > 0) continue; if (d2[(mask | u.fi)][v.fi] > newc + d2[mask][v.fi]) { //cout << u.se << " hop: " << v.fi << " 2mask " << u.fi << " " << mask << " ts " << d2[mask][v.fi] + newc << " " << d2[(mask | u.fi)][v.fi] << endl; d2[(mask | u.fi)][v.fi] = newc + d2[mask][v.fi]; pq.push({d2[(mask | u.fi)][v.fi], {(mask | u.fi), v.fi}}); } } } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> m; for (int i = 0; i < k; i ++) { cin >> ip[i]; } for (int i = 1; i <= m; i ++) { ll u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dij(); dij2(); ll ans = inf; //cout << endl; for (int i = 1; i <= n; i ++) { ans = min(ans, d2[(1 << k) - 1][i]); //cout << i << " " << d2[(1 << k) - 1][i] << endl; ll sum = 0; ///cout << i << " " << sum << endl; } 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...