• <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
            99久久精品免费看国产一区二区三区 | 国产精品一区二区久久不卡| 久久久久久国产精品无码下载| 国产精品99久久久精品无码| 人妻无码久久一区二区三区免费 | 欧美精品一区二区精品久久| 国产L精品国产亚洲区久久| 久久精品国产亚洲一区二区三区| 亚洲国产成人久久综合野外| 久久精品国产男包| 91亚洲国产成人久久精品| 伊色综合久久之综合久久| 99久久人妻无码精品系列| 久久久久九九精品影院| 久久人爽人人爽人人片AV| 国产精品永久久久久久久久久| 国产香蕉久久精品综合网| 国产精品久久久久国产A级| 婷婷久久精品国产| 99久久99久久精品国产片果冻| 久久久久久久波多野结衣高潮| 国产精品综合久久第一页| 国产午夜福利精品久久2021| 99久久做夜夜爱天天做精品| 久久久久女教师免费一区| 欧美精品一本久久男人的天堂| 无码国产69精品久久久久网站| 久久精品综合网| 久久久网中文字幕| 久久久久久久综合综合狠狠| 欧美伊香蕉久久综合类网站| 国产精品一区二区久久不卡| 久久精品www人人爽人人| 色综合久久中文字幕无码| 久久久久久久精品妇女99| 久久久久久国产a免费观看黄色大片 | 91精品国产色综久久| 久久九九有精品国产23百花影院| 精品久久人妻av中文字幕| 久久水蜜桃亚洲av无码精品麻豆| 老色鬼久久亚洲AV综合|