• <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>

            USACO Section 2.4 Bessie Come Home

            Bessie Come Home

            Kolstad & Burch

            It's dinner time, and the cows are out in their separate pastures. Farmer John rings the bell so they will start walking to the barn. Your job is to figure out which one cow gets to the barn first (the supplied test data will always have exactly one fastest cow).

            Between milkings, each cow is located in her own pasture, though some pastures have no cows in them. Each pasture is connected by a path to one or more other pastures (potentially including itself). Sometimes, two (potentially self-same) pastures are connected by more than one path. One or more of the pastures has a path to the barn. Thus, all cows have a path to the barn and they always know the shortest path. Of course, cows can go either direction on a path and they all walk at the same speed.

            The pastures are labeled `a'..`z' and `A'..`Y'. One cow is in each pasture labeled with a capital letter. No cow is in a pasture labeled with a lower case letter. The barn's label is `Z'; no cows are in the barn, though.

            PROGRAM NAME: comehome

            INPUT FORMAT

            Line 1: Integer P (1 <= P <= 10000) the number of paths that interconnect the pastures (and the barn)
            Line 2..P+1: Space separated, two letters and an integer: the names of the interconnected pastures/barn and the distance between them (1 <= distance <= 1000)

            SAMPLE INPUT (file comehome.in)

            5
            A d 6
            B d 3
            C e 9
            d Z 8
            e Z 3
            

            OUTPUT FORMAT

            A single line containing two items: the capital letter name of the pasture of the cow that arrives first back at the barn, the length of the path followed by that cow.

            SAMPLE OUTPUT (file comehome.out)

            B 11
            Analysis

            Since the problem aims to solve a single-source shortest path problem, we can use the classical algorithms, such as Dijkstra, Bellman-Ford and the Floyd algorithm. Thanks to the small data amount, all of them are correct for this prblem.

            Code

            /*
            ID:braytay1
            TASK:comehome
            LANG:C++
            */

            #include 
            <iostream>
            #include 
            <fstream>
            using namespace std;
            ifstream fin(
            "comehome.in");
            ofstream fout(
            "comehome.out");

            int map[55][55];
            int dis[55];

            void bellman_ford(){
                dis[
            52]=0;
                
            for (int k=1;k<52;k++)
                    
            for (int u=1;u<=52;u++)
                        
            for (int v=1;v<=52;v++)
                            
            if ((dis[v]>dis[u]+map[u][v])&&map[u][v]<=10000
                                dis[v]
            =dis[u]+map[u][v];
            }

            char find_min(int a[55]){
                
            char source;
                
            int min=1000000;
                
            for (int i=27;i<=51;i++){
                    
            if (min>a[i]) {min=a[i];source=i-26+64;}
                }

                
            return source;
            }

            int main(){
                
            int N;
                fin
            >>N;
                memset(map,
            100,sizeof(map));
                
            for (int i=1;i<=N;i++){
                    
            char source,dest;
                    fin
            >>source>>dest;
                    
            int s,d;
                    s
            =(source>=97&&source<=122)?(source-96):(source-64+26);
                    d
            =(dest>=97&&dest<=122)?(dest-96):(dest-64+26);
                    
            int ds;
                    fin
            >>ds;
                    
            if (ds<map[s][d]) map[s][d]=ds;        
                    map[d][s]
            =map[s][d];
                }

                memset(dis,
            100,sizeof(dis));
                bellman_ford();
                
            char res;
                res
            =find_min(dis);
                fout
            <<res<<" "<<dis[res-64+26]<<endl;
                
            return 0;
            }

            posted on 2008-08-19 22:19 幻浪天空領主 閱讀(222) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久综合亚洲色HEZYO社区| 久久天堂AV综合合色蜜桃网| 国产L精品国产亚洲区久久| 久久精品国产半推半就| 日韩亚洲欧美久久久www综合网| 久久www免费人成精品香蕉| 久久久这里只有精品加勒比| 99久久99这里只有免费费精品| 久久综合九色综合欧美狠狠| 久久亚洲视频| 久久免费高清视频| 无码专区久久综合久中文字幕| 国产成人久久777777| 亚洲精品美女久久久久99| 精品免费久久久久国产一区| 久久ZYZ资源站无码中文动漫| 久久久久久无码国产精品中文字幕| 亚洲av成人无码久久精品| 久久久综合香蕉尹人综合网| 91精品国产色综合久久| 狠狠色婷婷久久综合频道日韩| 草草久久久无码国产专区| 久久精品国产亚洲AV香蕉| 久久婷婷色综合一区二区| 国产激情久久久久影院老熟女免费| 久久夜色精品国产网站| 亚洲va久久久噜噜噜久久狠狠| 久久久久亚洲精品男人的天堂| 999久久久无码国产精品| 久久久久国产精品熟女影院| 亚洲综合精品香蕉久久网| 久久精品国产亚洲av瑜伽| 国产亚洲欧美精品久久久| 久久精品国产亚洲AV大全| 国产午夜福利精品久久2021 | 久久综合亚洲色HEZYO国产| 亚洲成人精品久久| 精品久久人人做人人爽综合| 精品乱码久久久久久夜夜嗨| 久久久久久久综合综合狠狠| 久久综合久久性久99毛片|