人活着系列之寻找最完美的人生

PRoblem Description

Input

Output

Example Input

121 2
Example Output
16
#include<stdio.h>#include<string.h>#define maxn 1002#define max 0x3f3f3f3fint df[maxn][maxn];//各个顶点之间的权值int book[maxn]; //标记顶点是否已经被遍历过的标记数组int dist[maxn];  //到某一顶点之间的最小权值,在程序运行时不断更新void prim(int n){    int i,j,pos,min,sum=0;    for(i=1;i<=n;i++)    {        dist[i]=df[1][i];    }    book[0]=1;    book[1]=1;    for(i=2;i<=n;i++)    {        pos=i;        min=max;        for(j=1;j<=n;j++)        {            if(!book[j]&&dist[j]<min)            {                min=dist[j];                pos=j;            }        }        sum+=min;        book[pos]=1;        for(j=1;j<=n;j++)        {            if(!book[j]&&dist[j]>df[pos][j])            {                dist[j]=df[pos][j];            }        }    }    printf("%d/n",sum);}int main(){    int i,j,t,n,u,v,w;    int a[maxn];    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        memset(book,0,sizeof(book));        memset(df,max,sizeof(df));        for(i=1;i<=n;i++)        {            scanf("%d",&a[i]);        }        for(i=1;i<=n;i++)        {            df[i][i]=0;        }        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                u=a[i]; v=a[j];                w=3*(u+v)+7;                df[i][j]=df[j][i]=w;            }        }        prim(n);    }    return 0;}