• <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 閱讀(148) 評論(0)  編輯 收藏 引用
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久99国产精品成人欧美| 日韩十八禁一区二区久久| 久久久久免费精品国产| 精品久久久久久亚洲精品| 国产精品内射久久久久欢欢 | 亚洲中文字幕伊人久久无码| 久久综合噜噜激激的五月天| 久久精品国产亚洲av瑜伽| 精品久久久噜噜噜久久久| 亚洲一本综合久久| 国产午夜免费高清久久影院| 亚洲一区二区三区日本久久九| 亚洲精品NV久久久久久久久久| 久久综合精品国产二区无码| 久久人人爽人人爽人人片AV麻豆| 久久99热精品| 久久99国产精品久久久| 一级做a爰片久久毛片看看| 狠狠色丁香婷婷综合久久来| 亚洲伊人久久综合影院| 国产成人综合久久久久久| 久久久精品人妻一区二区三区蜜桃| 久久久久亚洲av成人网人人软件 | 狠狠色丁香婷婷久久综合不卡 | 午夜欧美精品久久久久久久| 国产精品中文久久久久久久| 欧美黑人激情性久久| 91亚洲国产成人久久精品| 久久精品亚洲中文字幕无码麻豆| 日本精品久久久久影院日本| 精品久久久无码中文字幕天天| 99久久精品国内| 久久九九久精品国产| 伊人久久免费视频| www.久久热| 久久99热狠狠色精品一区| 久久狠狠色狠狠色综合| 无码超乳爆乳中文字幕久久| 久久亚洲精品人成综合网| 麻豆亚洲AV永久无码精品久久| 国产亚洲精品久久久久秋霞|