Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include".\template\headers.hpp"
- //#define MULTI_TASKCASE
- using namespace abb;
- using namespace output;
- using namespace rit;
- using namespace wit;
- inline void init() {
- }
- struct node {int b; ll w; node(int x, ll y): b(x), w(y) {}};
- bool operator<(node a, node b) {
- return a.w > b.w;
- }
- bool operator==(node a, node b) {
- return a.b == b.b && a.w == b.w;
- }
- inline void solve() {
- int n, m;
- cin >> n >> m;
- V<V<node>> edge(n), mst(n);
- while (m--) {
- static ll a, b, w;
- cin >> a >> b >> w, a--, b--;
- edge[a].emplace_back(b, w);
- edge[b].emplace_back(a, w);
- }
- V<ll> d(n, 1e15);
- V<int> p(n, -1);
- V<bool> vis(n, false);
- PQ<node> pq;
- pq.emplace(0, p[0] = d[0] = 0);
- for (int k = 0; k < n; k++) {
- static int a; a = ~0u;
- while (pq.size() && vis[a = pq.top().b]) pq.pop();
- if (!~a) break;
- vis[a] = true;
- for (const auto& i : edge[a])
- if (!vis[i.b] && i.w < d[i.b])
- pq.emplace(i.b, d[i.b] = i.w), p[i.b] = a;
- }
- ll mstp = accumulate(d.begin(), d.end(), 0ll);
- cout << mstp << ' ';
- for (int i = 1; i < n; i++) {
- mst[p[i]].emplace_back(i, d[i]);
- static int a, b, w;
- a = p[i], b = i, w = d[i];
- edge[a].erase(find(edge[a].begin(), edge[a].end(), node(b, w)));
- edge[b].erase(find(edge[b].begin(), edge[b].end(), node(a, w)));
- }
- V<V<node>> v(n, V<node>(__lg(n), {0, 0}));
- V<int> tin(n), tout(n);
- F<void(int, int, int)> build = [&](int cur, int pre, ll wt) {
- static int t = 0;
- tin[cur] = t++;
- for (int i = 0, k = pre; i < __lg(n); i++) {
- v[cur][i].b = k, v[cur][i].w = max(v[cur][i].w, wt);
- k = v[k][i].b, wt = v[k][i].w;
- }
- for (const auto& i : mst[cur])
- if (i.b != pre) build(i.b, cur, i.w);
- tout[cur] = t++;
- };
- auto isanc = [&](int a, int b) {
- return tin[a] <= tin[b] && tout[a] >= tout[b];
- };
- auto query = [&](int a, int b) {
- if (isanc(a, b)) return a;
- if (isanc(b, a)) return b;
- for (int i = __lg(n) - 1; i >= 0; i--)
- if (!isanc(v[a][i].b, b)) a = v[a][i].b;
- return v[a][0].b;
- };
- auto maxp = [&](int a, int b) {
- int anc = query(a, b);
- ll ret = 0;
- for (int i = __lg(n) - 1; i >= 0; i--) {
- if (!isanc(v[a][i].b, anc)) ret = max(ret, v[a][i].w), a = v[a][i].b;
- if (!isanc(v[b][i].b, anc)) ret = max(ret, v[b][i].w), b = v[b][i].b;
- }
- return ret;
- };
- build(0, 0, 0);
- ll diff = 1e18;
- for (int a = 0; a < n; a++)
- for (const auto& i : edge[a])
- diff = min(diff, i.w - maxp(a, i.b));
- cout << mstp + diff << endl;
- }
- main() {
- ios::sync_with_stdio(false);
- init();
- int t = 1;
- #ifdef MULTI_TASKCASE
- cin >> t; cin.ignore();
- #endif
- while (t--) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement