POJ 2387 Til the Cows Come Home Dijkstra求最短路径
Til the Cows Come Home
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
* 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
Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
Hint
There are five landmarks.
OUTPUT DETAILS:
Bessie can get home by following trails 4, 3, 2, and 1.
#include<stdio.h>
#include<string.h>
#include<limits.h> int a[][];
int dis[],b[];
int n; int min(int x,int y)
{
return x<y?x:y;
} void dij(int k)
{
int i,j,mind,minj;
memset(b,,sizeof(b));
for(i=;i<=n;i++){
dis[i]=INT_MAX;
}
dis[k]=;
for(i=;i<n;i++){
mind=INT_MAX;
for(j=;j<=n;j++){
if(!b[j]&&dis[j]<mind){
mind=dis[j];
minj=j;
}
}
b[minj]=;
for(j=;j<=n;j++){
if(!b[j]&&a[minj][j]>=){
dis[j]=min(dis[j],dis[minj]+a[minj][j]);
}
}
}
} int main()
{
int t,x,y,z;
memset(a,-,sizeof(a));
scanf("%d%d",&t,&n);
while(t--){
scanf("%d%d%d",&x,&y,&z);
if(a[x][y]!=-){
if(z<a[x][y]){
a[x][y]=z;
a[y][x]=z;
}
}
else{
a[x][y]=z;
a[y][x]=z;
}
}
dij();
printf("%d\n",dis[n]);
return ;
}
优化Dij:
#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<vector>
#include<queue>
using namespace std; struct Node{
int v,w;
friend bool operator<(Node a,Node b)
{
return a.w>b.w;
}
}node; vector<Node> a[];
int dis[];
int n; void dij(int k)
{
int v1,v2,i;
priority_queue<Node> q;
dis[k]=;
node.w=;
node.v=k;
q.push(node);
while(q.size()){
v1=q.top().v;
q.pop();
for(i=;i<a[v1].size();i++){
v2=a[v1][i].v;
if(dis[v2]>dis[v1]+a[v1][i].w){
dis[v2]=dis[v1]+a[v1][i].w;
node.w=dis[v2];
node.v=v2;
q.push(node);
}
}
}
} int main()
{
int t,x,y,z,i;
scanf("%d%d",&t,&n);
for(i=;i<=n;i++){
a[i].clear();
dis[i]=INT_MAX;
}
while(t--){
scanf("%d%d%d",&x,&y,&z);
node.w=z;
node.v=y;
a[x].push_back(node);
node.v=x;
a[y].push_back(node);
}
dij();
printf("%d\n",dis[n]);
return ;
}
最新文章
- (二)探究本质,WebGIS前端地图显示之地图比例尺换算原理
- Linux里的2>;&;1
- Web开发的常见面试题HTML和HTML5等
- Minimum Path Sum
- MyBatis学习总结_08_Mybatis3.x与Spring4.x整合
- 加快VisualStudio的开发速度--VS的一些开发技巧
- dispatch_get_current_queue 废弃
- Android应用程序请求SurfaceFlinger服务创建Surface的过程分析
- sockt初级了解 感悟 一起打怪升级偶
- 列表(list)之二 -运用篇 -快速生成规律性列表
- 网络协议 finally{ return问题 注入问题 jdbc注册驱动问题 PreparedStatement 连接池目的 1.2.1DBCP连接池 C3P0连接池 MYSQL两种方式进行实物管理 JDBC事务 DBUtils事务 ThreadLocal 事务特性 并发访问 隔离级别
- 运维chroot语法
- Java平台
- 原:Myeclipse10+Egit+bitbucket实现版本控制
- HDU 4122 单调队列
- Java中 方法的多态 简析图
- Nginx入门篇(四)之常用配置解析
- 按位与&;、按位或|、按位异或^
- 【Python3的进制扫盲】
- bat脚本运行py文件失败(一闪而过)
热门文章
- 九度OJ 1005:Graduate Admission (排序)
- Algorithm: Sieve of Eratosthenes
- python源码安装的包的卸载
- 在ubuntu怎样修改默认的编码格式
- plugin scala is incompatible with current installation
- [干货]兼容HTML5的Placeholder属性-更新版v0.10102013
- Linux_服务器_02_在linux上怎么看eclipse控制台输出语句
- Java的访问权限修饰符
- 第六章-jQuery
- darknet YOLOv2安装及数据集训练