#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define NN
#define M 1000000007 // 998244353
ll n;
vector<pl> adj[100010];
vector<ll> dijcache[100010];
vector<ll> dij(vector<ll> in) {
vector<ll> res(n+1);
vector<ll> dist(n+1, 1e18);
priority_queue<pl, vector<pl>, greater<pl>> q;
for (auto a: in) {
q.emplace(0, a);
dist[a] = 0;
}
while (q.size()) {
auto [d, h] = q.top(); q.pop();
if (dist[h] != d) continue;
for (auto [x, w]: adj[h]) if (dist[h] + w < dist[x]) {
dist[x] = dist[h] + w;
q.emplace(dist[x], x);
}
}
if (in.size() == 1) dijcache[in[0]] = dist;
return dist;
}
map<vector<ll>, pair<ll, vector<ll>>> cache;
pair<ll, vector<ll>> dfs(vector<ll> want) {
assert(want.size());
if (want.size() == 1) {
return {0, want};
} else if (want.size() == 2) {
if (cache.count(want)) return cache[want];
ll r = 1e18;
vector<ll> nodes;
F(i, 1, n+1) {
ll x = 0; for (auto d: want) x += dijcache[d][i];
if (x < r) nodes.clear(), r = x;
if (r == x) nodes.push_back(i);
}
return cache[want] = {r, nodes};
}
else if (want.size() <= 3) {
if (cache.count(want)) return cache[want];
ll r = 1e18;
ll optimalNode = -1;
F(i, 1, n+1) {
ll x = 0; for (auto d: want) x += dijcache[d][i];
if (x < r) {
r = x;
optimalNode = i;
}
}
auto dOpt = dij({optimalNode});
vector<ll> nodes;
F(i, 1, n+1) { // if any are optimal ,add this
for (auto d: want) if (dijcache[d][i] + dOpt[i] == dijcache[d][optimalNode]) {
nodes.push_back(i); break;
}
}
return cache[want] = {r, nodes};
} else {
// pick a partition of nodes to do
ll bans = 1e18; vector<ll> ansset;
bitset<100010> opt = {};
F(bm, 1, (1<<want.size())-1) {
vector<ll> w, w2;
F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
auto [r1, fixed_set1] = dfs(w);
auto [r2, fixed_set2] = dfs(w2);
bitset<100010> vis = {};
for (auto x: fixed_set1) vis[x] = 1;
bool fail = 0;
for (auto x: fixed_set2) if (vis[x]) {
fail = 1;
break;
}
if (fail) continue;
ll total = r1 + r2;
auto d3 = dij(fixed_set1); auto d4 = dij(fixed_set2);
ll ans = 1e18;
vector<ll> pot;
F(i, 1, n+1) {
if (d3[i] + d4[i] < ans) {
ans = d3[i] + d4[i]; pot.clear();
}
if (d3[i] + d4[i] == ans) pot.push_back(i);
}
ans += total;
if (bans > ans) {
bans = ans;
opt.reset();
for (auto x: fixed_set1) opt[x]=1;
for (auto x: fixed_set2) opt[x]=1;
for (auto x: pot) opt[x]=1;
}
}
F(i, 1, n+1) if (opt[i]) ansset.push_back(i);
return {bans, ansset};
}
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
cin >> n; G(k) G(m)
vector<ll> v(k); for (auto &x: v) cin >> x;
while (m--) {
G(x) G(y) G(w)
adj[x].emplace_back(y, w);
adj[y].emplace_back(x, w);
}
for (auto x: v) dij({x});
cout << dfs(v).K << '\n';
}
Compilation message
cities.cpp: In function 'std::pair<long long int, std::vector<long long int> > dfs(std::vector<long long int>)':
cities.cpp:22:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
| ^
cities.cpp:97:13: note: in expansion of macro 'F'
97 | F(i, 0, want.size()) (bool((1<<i)&bm) ? w: w2).push_back(want[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5124 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
21168 KB |
Output is correct |
| 2 |
Correct |
185 ms |
21744 KB |
Output is correct |
| 3 |
Correct |
59 ms |
14896 KB |
Output is correct |
| 4 |
Correct |
46 ms |
14216 KB |
Output is correct |
| 5 |
Correct |
136 ms |
19996 KB |
Output is correct |
| 6 |
Correct |
43 ms |
14160 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5208 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5408 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1086 ms |
26236 KB |
Output is correct |
| 2 |
Correct |
746 ms |
24188 KB |
Output is correct |
| 3 |
Correct |
319 ms |
19704 KB |
Output is correct |
| 4 |
Correct |
673 ms |
21964 KB |
Output is correct |
| 5 |
Correct |
207 ms |
15716 KB |
Output is correct |
| 6 |
Correct |
78 ms |
16208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6023 ms |
31768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
