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黄网站免费 | 亚洲免费不卡 | 青草香蕉精品视频在线观看 | 国产成人久久 | 狠狠色狠狠色综合 | 免费视频一区二区性色 | 青春禁区视频在线观看动漫版 | 免费高清成人啪啪网站 | 婷婷亚洲五月色综合 | 日韩小视频在线播放 | 久久专区 | 香蕉视频黄网站 | 久久精品国产精品亚洲毛片 | 国产成人久久精品一区二区三区 | 欧美成人毛片免费视频 | 久久精品男人的天堂 | 欧美国产伦久久久久 | 四虎免费永久在线播放 | 91手机看片国产永久免费 | 日韩欧美伦理 | 一级aa 毛片高清免费看 | 日韩欧美亚州 | 亚洲另类图 | 精品一区二区三区视频在线观看 | 国产亚洲精品久久久久久久网站 | 国产级a爱做片免费观看 | 久久精品全国免费观看国产 | 性夜影院爽黄a爽免费看网站 | 日本人成18在线播放 | 欧美视频在线一区二区三区 | 日韩精品视频观看 | 国产精品公开免费视频 | 久久综合视频网站 | 日本a在线 | 国语精品视频在线观看不卡 | 欧美成人aa大片拍拍拍 | 亚洲视频精选 | 国产成人a视频在线观看 | 亚洲美女在线观看播放 | 国产成人国产在线观看入口 | 成人激情视频 |