제출 #475472

#제출 시각아이디문제언어결과실행 시간메모리
475472fredbrCities (BOI16_cities)C++17
100 / 100
4409 ms41184 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define clr(x, c) memset((x), (c), sizeof((x))) using namespace std; template<class T> void DBG(T&& x) { cerr << x << " "; } template<class T, class...Args> void DBG(T&& x, Args&&... args) { DBG(x); DBG(args...); } #define DBG(...) do {cerr << "[" << #__VA_ARGS__ << "]: "; DBG(__VA_ARGS__); cerr << endl; } while (0) #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif template<class num> inline void rd(num& x) { char c, neg = 0; while(isspace(c = getchar_unlocked())); if(!isdigit(c)) neg = (c == '-'), x = 0; else x = c - '0'; while(isdigit(c = getchar_unlocked())) x = (x << 3) + (x << 1) + c - '0'; x = neg ? -x : x; } template <class Ty, class... Args> inline void rd(Ty& x, Args&... args) { rd(x); rd(args...); } using ll = long long; using ii = pair<ll, ll>; using Gr = vector<vector<ii>>; template<typename T = int> constexpr T inf = 0x3f3f3f3f; template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f; seed_seq seq { (uint64_t) chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now(). time_since_epoch()).count(), (uint64_t) __builtin_ia32_rdtsc(), (uint64_t) random_device{}(), (uint64_t) 17 }; mt19937 rng{seq}; template<class Ty> Ty randint(Ty a, Ty b) { return uniform_int_distribution<Ty>(a, b)(rng); } vector<ll> sssp(Gr const& g, int src = 0) { int const n = g.size(); vector<ll> dist(n, inf<ll>); vector<char> vis(n); priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push({0, src}); dist[src] = 0; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [v, w] : g[u]) { auto cost = d + w; if (cost < dist[v]) { dist[v] = cost; pq.emplace(cost, v); } } } return dist; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); int n, k, m; cin >> n >> k >> m; vector<int> cities(k); for (auto& i : cities) cin >> i; Gr g(n+1); for (int i = 0; i < m; i++) { int a, b, w; cin >> a >> b >> w; g[a].eb(b, w); g[b].eb(a, w); } if (k <= 2) { vector<vector<ll>> d; for (auto src : cities) d.push_back(sssp(g, src)); ll ans = inf<ll>; for (int i = 1; i <= n; i++) { ll cost = d[0][i] + d[1][i] + (k == 3? d[2][i] : 0); ans = min(ans, cost); } cout << ans << "\n"; } else { vector<int> perm(k); iota(all(perm), 0); ll ans = inf<ll>; vector<vector<ll>> d(k); for (int i = 0; i < k; i++) d[i] = sssp(g, cities[i]); do { if (k == 5) { if (perm[0] > perm[1] or perm[3] > perm[4] or perm[0] > perm[3]) continue; } if (k == 4) { if (perm[0] > perm[1]) continue; } vector<ll> ld = d[perm[0]]; for (int i = 1; i < k-1; i++) { int at = perm[i]; auto ng = g; for (int u = 1; u <= n; u++) ng[0].eb(u, ld[u] + d[at][u]); ld = sssp(ng); } for (int u = 1; u <= n; u++) { ll cost = ld[u] + d[perm[k-1]][u]; ans = min(ans, cost); } } while (next_permutation(all(perm))); cout << ans << "\n"; } }
#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...