Connect the Cities

水题，但是g++超时，c++对了 不解

#include<stdio.h>
const int MAXN=505;
const int INF=0x7fffffff;
int xx[MAXN];
int pre[MAXN];
int map[MAXN][MAXN];
int dist[MAXN];
int ans,n,flag;

void Prim()
{
    int i,j,k;
    int mn;
    bool p[MAXN];
    for(i=2;i<=n;i++)
    {
        p[i]=false;
        pre[i]=1;
        dist[i]=map[1][i];
    }
    dist[1]=0;
    p[1]=true;
    for(i=1;i<=n-1;i++)
    {
        mn=INF;
        k=0;
        for(j=1;j<=n;j++)
        {
            if(!p[j] && dist[j]<mn)
            {
                mn=dist[j];
                k=j;
            }
        }
        if(k==0) {flag=1; return ;}
        p[k]=true;
        ans+=dist[k];
        for(j=1;j<=n;j++)
        {
            if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
            {
                dist[j]=map[k][j];
                pre[j]=k;
            }
        }
    }
}

int main()
{
    int T;
    int m,k,t,i,j,a,b,c;
    int xx[MAXN];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(i==j) map[i][j]=0;
                    else map[i][j]=INF;
                }
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&a,&b,&c);
                if(map[a][b]>c) map[a][b]=map[b][a]=c;
            }
            for(i=0;i<k;i++)
            {
                scanf("%d",&t);
                for(j=0;j<t;j++)
                  scanf("%d",&xx[j]);
                for(j=1;j<t;j++)
                {
                    map[xx[j]][xx[j-1]]=map[xx[j-1]][xx[j]]=0;
                }
            }
            ans=flag=0;
            Prim();
            if(flag) printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

原文链接: https://www.cnblogs.com/zsboy/archive/2012/08/08/2628071.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍