Codeforces 1245 #Codeforces

1245D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf=0x3f3f3f3f3f3f3f3f;

const int maxn = 2e3 + 100;
ll x[maxn], y[maxn], k[maxn], c[maxn];
vector<pair<int, int> > connections;
vector<int> power_station;

void solve(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> x[i] >> y[i];
    for(int i=1; i<=n; i++) cin >> c[i];
    for(int i=1; i<=n; i++) cin >> k[i];

    vector<ll> dist(n + 1, inf);
    vector<bool> vis(n + 1, false);
    vector<int> parent(n + 1, 0);
    dist[0] = 0;
    ll ans = 0;

    for(int i=0; i<=n; i++){
        ll mn = -1;
        for(int j=0; j<=n; j++){
            if(vis[j]) continue;
            if(mn==-1 || dist[j] < dist[mn]) mn = j;
        }
        // cout << "vis: " << mn << " par " << dist[mn] << endl;
        vis[mn] = true;
        ans += dist[mn];
        if(parent[mn] == 0){
            if(mn != 0)
                power_station.push_back(mn);
        }else{
            connections.push_back({mn, parent[mn]});
        }

        for(int j=1; j<=n; j++){
            if(vis[j]) continue;
            ll dis = (mn==0?c[j]:(k[mn] + k[j]) * (abs(x[mn] - x[j]) + abs(y[mn] - y[j])));
            if(dis < dist[j]){
                dist[j] = dis;
                parent[j] = mn;
            }
        }
    }

    cout << ans << '\n' << power_station.size() << '\n';
    for(int i:power_station) cout << i << ' ';
    cout << '\n' << connections.size() << '\n';
    for(pair<int, int> pii:connections){
        cout << pii.first << ' ' << pii.second << '\n';
    }
}

signed main(){
    Android;

    solve();
}