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

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

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品www| av国内精品久久久久影院| 久久天天躁狠狠躁夜夜av浪潮| 99久久婷婷国产一区二区| 久久久久亚洲AV成人网| 2019久久久高清456| 一本大道加勒比久久综合| 国产精品99久久久久久董美香| 免费精品国产日韩热久久| 久久精品国产久精国产思思| 一本久久久久久久| 久久精品aⅴ无码中文字字幕不卡| 久久综合噜噜激激的五月天| 久久九色综合九色99伊人| 亚洲综合精品香蕉久久网| 国产高清美女一级a毛片久久w| 伊人色综合久久天天人守人婷| 97精品久久天干天天天按摩| 无码国内精品久久综合88 | 亚洲精品乱码久久久久久不卡| 中文字幕日本人妻久久久免费 | 漂亮人妻被中出中文字幕久久| 狠狠色丁香久久婷婷综合五月| 日日狠狠久久偷偷色综合免费| 精品久久久久久久中文字幕| 亚洲精品久久久www| 国产精品伊人久久伊人电影| 久久精品九九亚洲精品| 亚洲香蕉网久久综合影视| 亚洲综合伊人久久大杳蕉| 精品人妻伦九区久久AAA片69| 久久无码人妻精品一区二区三区 | 久久久久亚洲AV无码观看| 狠狠色丁香婷婷综合久久来来去| 日韩美女18网站久久精品| 久久久久久亚洲精品影院| 97r久久精品国产99国产精| 狠狠久久综合| 品成人欧美大片久久国产欧美...| 久久精品国产99久久久古代| 色综合久久中文字幕综合网|