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條評論
主站蜘蛛池模板: 亚洲欧美日韩高清一区二区一 | 色18美女社区 | 精品国产香蕉 | 亚洲欧美日韩中文字幕在线一区 | 久久99亚洲精品久久 | 一级毛片免费在线观看网站 | 奇米影视第四色777 奇米影视第四色7777 | 波多野结衣精品一区二区三区 | 国产成人精品男人的天堂538 | 另类 欧美 视频二区 | 免费一级在线 | 日韩视频一区二区 | 精品国产九九 | 久久精品国产一区二区三区 | 2020国产成人精品视频人 | 99热久久这里只精品国产ww | 中文国产成人精品久久96 | 毛片在线免费视频 | 春暖花开亚洲 | a级毛片视频 | 91福利国产在线观看一区二区 | 亚洲精品中文字幕乱码三区一二 | 中文精品久久久久国产不卡 | 中文字幕在线不卡精品视频99 | 伊人久久大香线蕉综合bd高清 | 狠狠躁夜夜躁人人爽天天段 | 国产福利一区二区在线观看 | 阿v天堂2017 啊用力嗯快国产在线观看 爱爱99 | 视频一区二区三区在线观看 | 天天射天天做 | 国产亚洲精品久久久久久牛牛 | 婷婷在线免费观看 | 精品国产综合成人亚洲区 | 天堂成人在线视频 | 深夜福利网站在线观看 | 国产日韩在线播放 | 日韩欧美国产高清在线观看 | 一区二区三区在线播放视频 | 精品欧美一区二区在线看片 | 国产一区二区日韩欧美在线 | 一级网站在线观看 |