nyoj-38-布线问题

2019-04-14 19:27发布

站内文章 / 模拟电子
12741 0 1758
#include
#define M 100000
int map[503][503];
int v,sum;
void prim()
{
    int used[503]={0},dis[503]={0};
    int i,j,k,min;
    sum=0;
    for(i=1;i<=v;i++)
    dis[i]=map[1][i];
    for(i=2;i<=v;i++)
    {
        min=M;
        for(j=2;j<=v;j++)
        if(min>dis[j]&&used[j]==0)
        {
            min=dis[j];
            k=j;
        }
        sum+=min;
        used[k]=1;
        for(j=1;j<=v;j++)
        if(used[j]==0&&dis[j]>map[k][j])
        dis[j]=map[k][j];
    }
} int main()
{
    int s,e;
    scanf("%d",&s);
    while(s--)
    {
        int i,j,a,b,c,t,min=M;
        scanf("%d%d",&v,&e);
        for(i=1;i<=v;i++)
        for(j=1;j<=v;j++)
        map[i][j]=M;
        for(i=0;i         {
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=map[b][a]=c;
        }
        for(i=0;i         {
            scanf("%d",&t);
            if(min>t)
            min=t;
        }
        prim();
        printf("%d ",sum+min);
    }
    return 0;
}

热门文章