• <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 幻浪天空領(lǐng)主 閱讀(223) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久九九全国免费| 国产精品久久久久久久久软件| 亚洲香蕉网久久综合影视| 久久久久亚洲av无码专区喷水| 久久精品国产亚洲AV大全| 99久久精品九九亚洲精品| 日韩美女18网站久久精品| 久久精品毛片免费观看| 久久亚洲中文字幕精品一区| 国产色综合久久无码有码| 国产精品18久久久久久vr | 久久精品国产精品国产精品污| 久久99国产一区二区三区| 无码久久精品国产亚洲Av影片| 国产精品99久久精品爆乳| 无码人妻久久一区二区三区免费丨| 99精品久久久久久久婷婷| 无码人妻久久一区二区三区免费 | 精品无码久久久久国产| 四虎久久影院| 国产精自产拍久久久久久蜜 | 国产免费久久精品丫丫| 国产精品久久久久9999| 狠狠色狠狠色综合久久| 亚洲综合久久夜AV | 久久久精品国产亚洲成人满18免费网站 | 久久夜色精品国产噜噜麻豆| 亚洲国产成人久久精品99| 久久成人国产精品二三区| 久久精品亚洲AV久久久无码| 亚洲国产高清精品线久久 | 精品多毛少妇人妻AV免费久久| 99久久精品免费国产大片| 国产成人久久精品一区二区三区| 日韩欧美亚洲综合久久| 欧美国产精品久久高清| 日韩欧美亚洲国产精品字幕久久久 | 久久久久久极精品久久久| 精品国产热久久久福利| 精品国产一区二区三区久久蜜臀| 国产精品美女久久久网AV|