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 幻浪天空领主 阅读(206) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2024年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜