POj2387——Til the Cows Come Home——————【最短路】
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
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<algorithm>
using namespace std;
const int maxn=1200;
const int INF=1e9;
bool vis[maxn];
int d[maxn];
int w[maxn][maxn];
int T,N;
void Dijkstra(int st){ for(int i=0;i<N;i++){ int x,m=INF;
for(int y=N;y>=1;y--){ if(!vis[y]&&d[y]<=m)
m=d[x=y];
}
vis[x]=1;
for(int y=N;y>=1;y--){ d[y]=min(d[y],d[x]+w[x][y]);
}
}
printf("%d\n",d[1]);
}
void init(){ for(int i=0;i<=N;i++){ d[i]=(i==N?0:INF);
for(int j=0;j<=N;j++){ if(i==j)
w[i][j]=0;
else
w[i][j]=w[j][i]=INF;
}
}
memset(vis,0,sizeof(vis));
}
int main(){ while(scanf("%d%d",&T,&N)!=EOF){ init();
for(int i=1;i<=T;i++){ int u,v,dw;
scanf("%d%d%d",&u,&v,&dw);
w[u][v]=w[v][u]=min(dw,w[u][v]);//去重
}
Dijkstra(N);
}
return 0;
}
最新文章
- U盘容量变小解决办法
- DotNetOpenAuth使用笔记
- js判断页面是pc打开还是手机打开
- PHP slim restfull框架nginx 配置
- CentOS7安装mysql数据库
- 移动web调式利器---Rosin研究
- Swift语言学习之学习资源
- LTIB常用命令1
- Android子线程更新主界面
- CSS3 总结-2
- unity3D游戏开发十八之NGUI动画
- Linux部署与基本指令
- C语言第二次作业 ,
- scrapy学习笔记(1)
- subline 建立服务器
- pom.xml文件释义
- git status -s命令解析
- 微信小程序获取用户手机号详解
- parallels Desktop解决无法压缩硬盘的问题
- 配置ssh的config文件-为每个ssh连接创建别名