constintMAXN=505;constintINF=0x7fffffff;intxx[MAXN];intpre[MAXN];intmap[MAXN][MAXN];intdist[MAXN];intans,n,flag;voidPrim(){inti,j,k;intmn;boolp[MAXN];for(i=2;i<=n;i++){p[i]=false;pre[i]=1;dist[i]" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Connect the Cities

系統 1887 0

水題,但是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
      
      
        ;

}
      
    

Connect the Cities


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久草热视频在线 | 日本人69视频jizz免费看 | 免费又爽又黄禁片视频在线播放 | 精品三级国产一区二区三区四区 | 欧美大黄大色一级毛片出红 | 91精品国产91热久久p | 在线观看亚洲成人 | 日本1区二区三区公司 | 欧美男女啪啪 | 亚洲精品短视频 | 真实子伦视频不卡 | 欧美在线日韩在线 | 日韩国产成人精品视频 | 97精品视频在线观看 | 麻豆国产精品高中生视频 | 一级女人毛片 | 久久天天躁狠狠躁夜夜躁 | 久久香蕉网 | 奇米色奇米 | 欧美亚洲国产另类 | 996re免费热在线视频手机 | 中文字幕日韩一区二区 | 国产一级特黄aa级特黄裸毛片 | 波多野结衣中文字幕一区 | 特级女人十八毛片a级 | 久久久久女人精品毛片 | 亚洲国产精品视频在线观看 | 成人在线免费视频播放 | 日韩精品影视 | 日本亚洲一区二区三区 | 久久成人免费 | 午夜狠狠操 | 午夜不卡福利 | 欧美色射| 伊人不卡久久大香线蕉综合影院 | 国产一区二区不卡视频 | 欧美一级免费片 | 澳门成人免费永久视频 | 爱爱永久免费视频网站 | 欧美激情在线一区二区三区 | 四虎一区 |