Shichikuji and Power Grid CodeForces - 1245D【最小生成树-点权变边权-超级源点】

没有做过这种题目，所以当时就没有做出来，其实即使建立一个超级源点，和每个点相连，以建发电站的费用为边权，其他的点之间的边权就按题目给的算。然后跑一遍最小生成树即可，我用的是prim。注意数据范围(>_<),因为这个一直WA。

#include <bits/stdc++.h>//注意数据范围long long
using namespace std;
const int N=2e3+5;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll pic[N][N];
int x[N],y[N],c[N],k[N],pre[N];
ll dis[N];
bool vis[N];
struct node
{
    int id;
    ll d;
    int pre;
    friend bool operator <(node a,node b)
    {
        return a.d>b.d;
    }
};
priority_queue<node>que;
vector<pair<int,int> >res[2];
ll prim(int n)
{
    ll ans=0;
    for(int i=0;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=0;
        pre[i]=i;
    }
    dis[0]=0;
    while(!que.empty())
        que.pop();
    que.push({0,0,0});
    while(!que.empty())
    {
        node now=que.top();
        que.pop();
        if(vis[now.id])
            continue;
        for(int i=0;i<=n;i++)
        {
            if(i!=now.id)
            {
                if(dis[i]>pic[now.id][i])
                {
                    dis[i]=pic[now.id][i];
                    if(!vis[i])
                        que.push({i,dis[i],now.id});
                }
            }
        }
        vis[now.id]=1;
        ans+=now.d;
        pre[now.id]=now.pre;
    }
    return ans;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        res[0].clear();
        res[1].clear();
        for(int i=1;i<=n;i++)
            scanf("%d%d",&x[i],&y[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&k[i]);
        for(int i=1;i<=n;i++)
        {
            pic[0][i]=c[i];
            pic[i][0]=c[i];
            for(int j=1;j<=n;j++)
                pic[i][j]=(ll)(k[i]+k[j])*(abs(x[i]-x[j])+abs(y[i]-y[j]));//没有进行强制类型转换，WA了6发
        }
        printf("%lld\n",prim(n));
        for(int i=1;i<=n;i++)
        {
            if(pre[i]==0)
                res[0].push_back({0,i});
            else
                res[1].push_back({pre[i],i});
        }
        printf("%d\n",res[0].size());
        for(int i=0;i<res[0].size();i++)
            printf("%d%c",res[0][i].second,i==res[0].size()-1?'\n':' ');
        printf("%d\n",res[1].size());
        for(int i=0;i<res[1].size();i++)
            printf("%d %d\n",res[1][i].first,res[1][i].second);
    }
    return 0;
}