• <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 - 74,  comments - 33,  trackbacks - 0
            ChiBi

            Time Limit: 5 Seconds      Memory Limit: 32768 KB

            watashi's mm is so pretty as well as smart. Recently, she has watched the movie Chibi. So she knows more about the War of ChiBi. In the war, Cao Cao had 800,000 soldiers, much more than his opponents'. But he was defeated. One of the mistakes he made was that he connected some of his boats together, and these boats were burned by the clever opponents.

            Then an interesting problem occurs to watashi's mm. She wants to use this problem to check whether watashi is as smart as her. However, watashi has no idea about the problem. So he turns to you for help.

            You know whether two boats are directly connected and the distance between them. And Fire's speed to spread between boats is 1m/s. You also know the time your soldiers need to travel from your camp to each boat. Because burning Cao Cao's boat is a very dangerous job, you must choose the least number of soldiers, and each one can only burn one boat. How much time do you need to burn all the Cao Cao's boats?

            Input

            The input contains several test cases. Each test case begins with a line contains only one integer 0 <= N <= 1000, which indicates the number of boats. The next N lines, each line contains N integers in range [0, 10000], the jth number in the ith line is the distance in metre between the ith boat and the jth boat, if the number is -1, then these two boats are not directly connected (d(i, j) == d(j, i) && d(i, i) == 0). Then N intergers in range [0, 10000], the ith number is the time in second your soldiers need to travel from the camp to the ith boat. What's more Cao Cao is not that stupid, so he won't connect more than 100 boats together.

            Output

            The shortest time you need to burn all the Cao Cao's boats counting from the soldiers leave the camp in a single line.

            Sample input

            4
            0 1 2 -1
            1 0 4 -1
            2 4 0 -1
            -1 -1 -1 0
            1 2 4 8
            

            Sample Output

            8
            該死的-1 我一直調試的代碼最后發現自己的-1居然沒處理
            暈死
            代碼如下
             1#include<stdio.h>
             2int map[1010][1010],flag[1010];
             3int time[1010];
             4int main()
             5{
             6    int n,i,j,k,sum,min;
             7    while(scanf("%d",&n)!=EOF)
             8    {
             9        for(i=0;i<n;i++)
            10        {
            11            for(j=0;j<n;j++)
            12                scanf("%d",&map[i][j]);
            13            flag[i]=0;
            14        }

            15        for(i=0;i<n;i++)
            16            scanf("%d",&time[i]);
            17        for(k=0;k<n;k++)
            18            for(i=0;i<n;i++)
            19                if(i!=k&&map[i][k]>=0)
            20                    for(j=0;j<n;j++)
            21                        if(j!=k&&map[k][j]>=0)
            22                        {
            23                            if(map[i][j]==-1)map[i][j]=map[i][k]+map[k][j];
            24                            else if(map[i][k]+map[k][j]<map[i][j])map[i][j]=map[i][k]+map[k][j];
            25                        }

            26        for(i=0;i<n;i++)
            27        {
            28            int max=0;
            29            for(j=0;j<n;j++)
            30                if(map[i][j]>max)max=map[i][j];
            31            time[i]+=max;    
            32        }

            33        sum=0;
            34        for(i=0;i<n;i++)
            35        {
            36            if(!flag[i])
            37            {
            38                flag[i]=1;
            39                min=time[i];
            40                for(j=0;j<n;j++)
            41                    if(map[i][j]>=0&&!flag[j])
            42                    {
            43                        flag[j]=1;
            44                        if(min>time[j])min=time[j];    
            45                    }

            46            }

            47            if(sum<min)sum=min;    
            48        }

            49        printf("%d\n",sum);            
            50    }
                
            51}

            52Floyd思路
            posted on 2008-12-27 14:42 KNIGHT 閱讀(147) 評論(0)  編輯 收藏 引用
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            免费一级欧美大片久久网| 热re99久久6国产精品免费| 久久精品女人天堂AV麻| 国产精品99久久久久久董美香| 国产成人精品久久| 欧美亚洲国产精品久久久久| 亚洲国产欧美国产综合久久| 国产精品久久久久久影院 | 久久久久国产精品| 国产精品伊人久久伊人电影| 久久久久久久综合狠狠综合| 亚洲国产欧美国产综合久久| 久久精品视屏| 久久精品男人影院| 久久久久无码精品国产| 色偷偷888欧美精品久久久| 亚洲日韩中文无码久久| 久久久久亚洲精品中文字幕| 久久国产精品久久精品国产| 伊人久久精品无码av一区| 久久综合久久鬼色| 亚洲狠狠综合久久| 精品久久久久久久无码| 午夜精品久久久久久影视777| 国产一久久香蕉国产线看观看| 亚洲欧美另类日本久久国产真实乱对白| 亚洲国产天堂久久综合| 久久777国产线看观看精品| 久久久久亚洲精品日久生情| 久久强奷乱码老熟女| 91精品观看91久久久久久| 国产精品99久久精品| 国产精品美女久久久久久2018| 亚洲精品午夜国产va久久| 99久久国语露脸精品国产| 亚洲国产精品高清久久久| 国产99久久久国产精品小说| 国产69精品久久久久APP下载| 久久久久婷婷| 中文精品99久久国产 | 老司机国内精品久久久久|