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

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品人成免费| 中文字幕一区二区三区久久网站| 精品久久久久久久国产潘金莲| 久久免费视频一区| 亚洲色婷婷综合久久| 九九久久99综合一区二区| 97久久精品人人澡人人爽| 久久国产精品波多野结衣AV| 久久综合给久久狠狠97色| 久久久久综合国产欧美一区二区| 无码乱码观看精品久久| 国产成人久久激情91| 中文字幕乱码久久午夜| 久久se精品一区二区| 亚洲精品午夜国产va久久| 91精品国产91久久久久久蜜臀| 久久狠狠一本精品综合网| 韩国三级大全久久网站| 中文国产成人精品久久亚洲精品AⅤ无码精品| 新狼窝色AV性久久久久久| 久久久久精品国产亚洲AV无码| 久久人人超碰精品CAOPOREN| 国产成人久久AV免费| 国产精品久久国产精品99盘| 日本五月天婷久久网站| 久久精品成人一区二区三区| 久久综合久久综合九色| 久久这里只精品国产99热| 亚洲AV日韩AV永久无码久久| 久久久亚洲裙底偷窥综合| 久久九九久精品国产| 狠狠色丁香久久婷婷综合| 久久亚洲欧洲国产综合| 国产三级观看久久| 伊人久久无码精品中文字幕| 国产精品欧美亚洲韩国日本久久 | 亚洲va国产va天堂va久久| 亚洲国产香蕉人人爽成AV片久久 | 中文字幕久久亚洲一区| 三级片免费观看久久| 青青热久久国产久精品|