注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【POJ2387】Til the Cows Come Home  

2013-05-09 13:45:58|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Til the Cows Come Home
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 23232Accepted: 7797

Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible. 

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it. 

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.

Input

* Line 1: Two integers: T and N 

* Lines 2..T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1..100.

Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

Sample Output

90

Hint

INPUT DETAILS: 

There are five landmarks. 

OUTPUT DETAILS: 

Bessie can get home by following trails 4, 3, 2, and 1.

这题是简单的最短路径算法求固定两点之间的最短距离的应用题,可以采用最简单的dijkstra算法。。。
唯一要注意的就是:输入的路径中可能存在重边,需要判断当前输入的路径权值是否比之前的小,取最小的那个权值。。。

#define MAXSIZE 1000 #define INFINITE 99999999 #define min(a,b) a<b?a:b #include <iostream> using namespace std; unsigned int shortest_weight(unsigned int matrix[][MAXSIZE],unsigned short int a,unsigned short int b,unsigned short int N) { unsigned int dist[MAXSIZE]; bool accessed[MAXSIZE]; unsigned short min_label; for(int i=0;i<N;i++) { dist[i]=matrix[N-1][i]; accessed[i]=false; } accessed[a]=true; while(1) { unsigned int minimum=INFINITE; min_label=a; for(int i=0;i<N;i++) { if(accessed[i]==false&&dist[i]<minimum) { minimum=dist[i]; min_label=i; } } if(min_label==a) { break; } accessed[min_label]=true; for(int i=0;i<N;i++) { if(accessed[i]==false&&dist[i]>(dist[min_label]+matrix[min_label][i])) { dist[i]=dist[min_label]+matrix[min_label][i]; } } } return dist[b]; } int main() { unsigned short int T,N; unsigned short int a,b,weight; cin>>T>>N; unsigned int (*matrix)[MAXSIZE]=new unsigned int[MAXSIZE][MAXSIZE]; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { matrix[i][j]=INFINITE; } } while(T--) { cin>>a>>b>>weight; matrix[a-1][b-1]=matrix[b-1][a-1]=min(weight,matrix[b-1][a-1]); //比较重边权值 } unsigned int min_dist=shortest_weight(matrix,N-1,0,N); cout<<min_dist<<endl; return 0; }

  评论这张
 
阅读(297)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017