lessons/参考实现/06-最小与最大生成树/CodeForces-1245D.cpp

#include <iostream>
#include <limits>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<long long> x(n), y(n), c(n), k(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
    for (auto &v : c) cin >> v;
    for (auto &v : k) cin >> v;
    vector<long long> best = c;
    vector<int> parent(n, -1); vector<bool> used(n, false);
    vector<int> stations; vector<pair<int, int>> wires;
    long long total = 0;
    for (int step = 0; step < n; ++step) {
        int v = -1;
        for (int i = 0; i < n; ++i) if (!used[i] && (v == -1 || best[i] < best[v])) v = i;
        used[v] = true; total += best[v];
        if (parent[v] == -1) stations.push_back(v);
        else wires.push_back({v, parent[v]});
        for (int to = 0; to < n; ++to) if (!used[to]) {
            long long cost = (k[v] + k[to]) * (abs(x[v] - x[to]) + abs(y[v] - y[to]));
            if (cost < best[to]) best[to] = cost, parent[to] = v;
        }
    }
    cout << total << '\n' << stations.size() << '\n';
    for (int v : stations) cout << v + 1 << ' ';
    cout << '\n' << wires.size() << '\n';
    for (auto [u, v] : wires) cout << u + 1 << ' ' << v + 1 << '\n';
}