Topic introduction

Magic array.
Title Description
There are n cities on the plane, numbered 1 ∼ n.

The location coordinates of the ith city are (xi,yi).

The locations of different cities may overlap.

Now it is necessary to electrify every city by building power stations and wires.

If a city has a power station or is directly or indirectly connected with the city with a power station through wires, the city will be powered on.

The cost of building a power station in city i is ci yuan.

The cost of building wires between city i and city j is ki+kj yuan per unit length.

Wires can only extend in four directions: up, down, left and right. Wires can cross each other. Wires are two-way.

Each wire is built from one city to another along the shortest route.

That is, if a wire is built between city i and city j, the length of the wire is | xi − XJ + | Yi − yj (|... | represents the absolute value).

Excuse me, how to reasonably design the power on scheme so that all cities can be successfully powered on at the least cost?

Output the least cost and specific scheme.

If the scheme is not unique, any reasonable scheme can be output.

Input format
The first line contains the integer n.

Next, line n, where line i contains two integers Xi and Yi to describe the abscissa and ordinate of city i.

The next line contains n integers c1,c2,..., cn to describe the cost of building power stations in each city.

The last line contains n integers k1,k2,..., kn.

Output format
The minimum cost of the first line of output.

The second line outputs an integer v, indicating the number of power stations to be established.

The third line outputs v integers, indicating the city number of the power station. Note that the output number should be within the range [1,n]. And the output number shall not be repeated. The output number sequence is arbitrary.

The fourth line outputs an integer e, indicating the number of wires to be built.

Next, in line e, two integers a and B are output in each line, indicating that a wire is to be built between cities a and B. Note that only one wire needs to be built between any two cities, that is, for each (a,b), there should be no redundant (a,b) or (b,a) output. A and B cannot be the same and must be within the range [1,n]. The order of output wires is arbitrary.

If the answer is not unique, output any reasonable scheme.

Data range
For the first three test points, 1 ≤ n ≤ 3.
For all test points, 1 ≤ n ≤ 2000, 1 ≤ xi, yi ≤ the 6th power of 10, 1 ≤ ci, ki ≤ the 9th power of 10.

Input example 1:
3
2 3
1 1
3 2
3 2 3
3 2 3

Input example 2:
3
2 1
1 2
3 3
23 2 23
3 2 3

Problem solving ideas

The meaning of the title
Give us n villages, numbered 1-n. if the village wants to live, it has to use electricity. There are two ways to do electricity. First, we do electricity ourselves. Why? We build a power station ourselves at a cost of c[i]. Second, where can we steal electricity? Doesn't someone have a power station? Hey, hey, hey, but it still costs to get electricity from other villages. We have to buy wires. The wire per unit is ki+kj and the length is | xi − XJ + | Yi − yj (|... | indicates absolute value). How can we spend the least?

We can find that if we want to power on all villages, it is equal to all points, that is, the village is in a connected block. In this way, it is a problem of minimum spanning tree (dog head). How to compose the picture? What is the edge?

We regard the first method of building a power station as a super power station, which is zero point. If a village wants to choose the first power generation method, it is connected with me (zero point) and costs c[i]
The second is the connection between villages, which costs (ki+kj) * |xi − xj|+|yi − yj|
These two methods are the way to establish the edge between two points
Here comes the problem
We also need to know which villages build power stations. Those villages are connected with other villages, so we use
vector < int > ans1;// Point connected to super power station
vector< PII> ans2;// The edge between villages

ps: we should be patient when facing long problems (look at the long problems, they are really manic)
Upper code

code implementation

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010;

int n;
PII q[N];//The abscissa and ordinate of the storage point
int wc[N];//Describe the cost of building power stations in each city
int wk[N];//The cost of building wires between city i and city j is ki+kj yuan per unit length
int dist[N];//The cost of building power stations in cities
int distp[N];//Point connected to connection block
bool st[N]; //Is it in the connection block
vector<int> ans1;//Point connected to super power station
vector<PII> ans2;//The edge between villages

inline LL get_distance(int a,int b) //Find the cost of connecting two points. Because the function is called many times, use inline to speed up the speed
{
    int x=q[a].x-q[b].x;
    int y=q[a].y-q[b].y;
    return (LL) (abs(x)+abs(y)) * ( wk[a]+wk[b]);
}

LL prim()
{
    LL res=0;
    dist[0] = 0; //Suppose point 0 is a super power station, and all points to be built are connected to this point
    st[0]=true;//Put the super power station into the Unicom block
    for(int i = 1;i <= n;i ++) dist[i]=wc[i];//Suppose that every point, that is, all villages are connected to the super power station
    
    for (int i = 0; i < n; i ++ )//Add the remaining n points to the connection block
    {
        int t=-1; //Indicates adding points to connected blocks
        for (int j = 1; j <= n; j ++ )//Find the point closest to the Unicom block
            if(!st[j] && (t==-1 || dist[j]<dist[t]))
                t = j;
        st[t]=true;
        res += dist[t];
        if(!distp[t]) ans1.push_back(t);//If the point connected to point t is zero, then add ans1
        else ans2.push_back({distp[t],t});//Otherwise, it is connected to the village
        for (int j = 1; j <= n; j ++ )//Cost of updating all other points
            if(!st[j] && dist[j] > get_distance(t,j))
            {
                dist[j]=get_distance(t,j);
                distp[j]= t;
            }
    }
    return res;
}

int main()
{
    scanf("%d", &n);//point
    for (int i = 1; i <= n; i ++ ) scanf("%d%d",&q[i].x,&q[i].y);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &wc[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &wk[i]);
    
    LL res = prim();
    printf("%lld\n", res);
    printf("%d\n", ans1.size());
    for(auto x: ans1) printf("%d ",x);
    puts("");
    printf("%d\n", ans2.size());
    for (auto& t: ans2)
        printf("%d %d\n", t.x, t.y);
    return 0;
}

ps: why is dist array not long but int? At the beginning, we assume that all points are connected to the super power station, and its cost will not exceed int. it will be updated only if it costs less than wc[i], that is, connected to the super power station. Therefore, it is not necessary to use the definition of long long