USACO--AOJ Bessie Come Home --Floyd算法

Bessie Come Home

Time Limit:JAVA/Others2000/1000MS  Memory Limit:JAVA/Others131072/65536KB
Total Submit:6 Accepted:2

Description

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.

Input

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)

Output

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 Input

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

Sample Output

B 11

 1Floyd 算法:http://icpc.ahu.edu.cn:8080/AOJ/   做的第一个图论题
 2图的最短路径问题,到‘Z’的最短路径;
 3Floyd算法大概知道怎么用了 ,好像是动态规划实现的,不知道为什么这样是对的
 4O(N^3)求解最短路径问题,数据范围超过400可能就危险了
 5#include<iostream>
 6#include<string.h>
 7using namespace std;
 8int dis[53][53];
 9const int INF=10000000;
10void Floyd(int n)
11{
12     for(int k=1; k<=n; k++)
13     for(int i=1; i<=n; i++)
14     for(int j=1; j<=n; j++)
15      if(i!=k&&k!=j&&i!=j&&dis[i][k]+dis[k][j]<dis[i][j])
16      dis[i][j]=dis[i][k]+dis[k][j];
17
18}

19
20
21int main()
22{
23    int p,i,j,k,d,n1,n2; 
24    cin>>p;
25    memset(dis,0,sizeof (dis));
26    for(i=1; i<=52; i++)
27    for(j=1; j<=52; j++)
28    dis[i][j]=INF;
29     
30    for(i=1; i<=p; i++)
31    {
32       char v1,v2;
33       cin>>v1>>v2>>d;      
34       if(v1==v2)continue;
35       n1=(v1>='a'?v1-'a'+1:v1-'A'+26+1);
36       n2=(v2>='a'?v2-'a'+1:v2-'A'+26+1);
37       if(d<dis[n1][n2])dis[n1][n2]=dis[n2][n1]=d;
38    }

39    
40    Floyd(52);
41    
42    int min=INF+100;
43    char c;
44    for(i=27; i<=51; i++//大写字母到Z 
45    {
46       if(dis[i][52]<min){min=dis[i][52];c=i; }
47    }

48    cout<<char(c-27+'A')<<' '<<min<<endl;
49    //system("pause");
50    return 0;
51}

52

posted on 2010-05-23 20:03 田兵 阅读(1251) 评论(1)  编辑 收藏 引用 所属分类: 图论题


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2019年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜