• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 100,  comments - 15,  trackbacks - 0
            //每對頂點之間的最短路徑算法floyd,其實是動歸,O(n3),還要注意disjoint
            #include<iostream>
            using namespace std;
            #define M 100
            #define INF 20000000

            int sb[M+1][M+1];
            int d[M+1][M+1];
            int n;
            int i,j,k;

            void Init()
            {
                
                
            for(i=1;i<=n;i++)
                    
            for(j=1;j<=n;j++)
                        sb[i][j]
            =(i==j?0:INF);
            }



            void floyd()
            {
                
            for(i=1;i<=n;i++)
                    
            for(j=1;j<=n;j++)
                        d[i][j]
            =sb[i][j];
                
            for(k=1;k<=n;k++)
                    
            for(i=1;i<=n;i++)
                        
            for(j=1;j<=n;j++)
                            
            if(d[i][k]+d[k][j]<d[i][j])
                                d[i][j]
            =d[i][k]+d[k][j];
            }

            int main()
            {
                
            int mi,v,w,ri,min,max;
                
            while( scanf("%d",&n)==1 && n!=0)
                
            {
                    Init();
                    
            for(i=1;i<=n;i++)
                    
            {    
                        scanf(
            "%d",&mi);
                        
            for(j=1;j<=mi;j++{ scanf("%d%d",&v,&w); sb[i][v]=w; }
                    }

                    floyd();
                    min
            =INF;
                    ri
            =-1;
                    
            for(i=1;i<=n;i++)
                    
            {
                        max
            =0;
                        
            for(j=1;j<=n;j++)
                            
            if(d[i][j]>max) max=d[i][j];
                        
            if(max<min) { min=max;ri=i;}
                    }

                    
            if(ri==-1) printf("disjoint\n");
                    
            else printf("%d %d\n",ri,min);
                }

                
            return 0;
            }
            posted on 2009-05-24 16:17 wyiu 閱讀(203) 評論(0)  編輯 收藏 引用 所屬分類: POJ
            国产精品久久亚洲不卡动漫| 久久久久女教师免费一区| 无码人妻久久一区二区三区蜜桃 | 国产精品无码久久四虎| 久久久精品免费国产四虎| 久久久精品视频免费观看| 欧美国产成人久久精品| 久久精品国内一区二区三区| 午夜精品久久久久久影视777| 亚洲精品高清国产一线久久| 久久久久久久99精品免费观看| 久久人人爽人人爽人人片AV麻烦| 东京热TOKYO综合久久精品| 亚洲?V乱码久久精品蜜桃| 国产精品久久久久久久久鸭| 欧美黑人激情性久久| 久久99国产一区二区三区| 亚洲精品乱码久久久久久按摩| 99久久www免费人成精品| 奇米影视7777久久精品| 伊人热热久久原色播放www| 潮喷大喷水系列无码久久精品| 久久午夜免费视频| 日本久久中文字幕| 久久久久国产一区二区三区| 人人狠狠综合久久亚洲婷婷| 精品无码久久久久久午夜| 97精品伊人久久久大香线蕉 | 国产午夜精品久久久久九九电影| 亚洲AV日韩AV天堂久久| 伊人久久大香线蕉综合网站| 久久亚洲欧洲国产综合| 国产午夜精品久久久久九九| 国产精品久久免费| 狠狠久久亚洲欧美专区| 99久久免费国产精品热| AV色综合久久天堂AV色综合在| 久久99精品久久久久久hb无码 | 久久久久青草线蕉综合超碰| 一级女性全黄久久生活片免费 | AA级片免费看视频久久|