| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 475478 |
2021-09-22T15:21:03 Z |
fredbr |
Cities (BOI16_cities) |
C++17 |
|
2357 ms |
33844 KB |
#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;
// }
vector<ll> sssp(Gr const& g, int src = 0) {
int const n = g.size();
vector<ll> dist(n, inf<ll>);
deque<int> pq;
pq.push_back(src);
dist[src] = 0;
while (!pq.empty()) {
auto u = pq.front();
pq.pop_front();
for (auto [v, w] : g[u]) {
auto cost = dist[u] + w;
if (cost < dist[v]) {
dist[v] = cost;
if (pq.empty() or cost <= dist[pq.front()])
pq.emplace_front(v);
else
pq.emplace_back(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-2; 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-2]][u] + d[perm[k-1]][u];
ans = min(ans, cost);
}
} while (next_permutation(all(perm)));
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
316 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
16352 KB |
Output is correct |
| 2 |
Correct |
216 ms |
16176 KB |
Output is correct |
| 3 |
Correct |
113 ms |
10988 KB |
Output is correct |
| 4 |
Correct |
85 ms |
9152 KB |
Output is correct |
| 5 |
Correct |
169 ms |
14860 KB |
Output is correct |
| 6 |
Correct |
81 ms |
9116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
588 KB |
Output is correct |
| 2 |
Correct |
4 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
3 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
918 ms |
30856 KB |
Output is correct |
| 2 |
Correct |
727 ms |
30124 KB |
Output is correct |
| 3 |
Correct |
956 ms |
22632 KB |
Output is correct |
| 4 |
Correct |
554 ms |
23300 KB |
Output is correct |
| 5 |
Correct |
205 ms |
16532 KB |
Output is correct |
| 6 |
Correct |
147 ms |
17736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2007 ms |
33844 KB |
Output is correct |
| 2 |
Correct |
2139 ms |
32604 KB |
Output is correct |
| 3 |
Correct |
1432 ms |
32324 KB |
Output is correct |
| 4 |
Correct |
2357 ms |
24252 KB |
Output is correct |
| 5 |
Correct |
1180 ms |
23760 KB |
Output is correct |
| 6 |
Correct |
329 ms |
16636 KB |
Output is correct |
| 7 |
Correct |
241 ms |
17752 KB |
Output is correct |
