把母牛带回家
**时间限制:
** 1000MS
**内存限制:
** 65536K
**总提交:
** 59466
**接受:
** 20214
描述
Bessie在野外出来,想要回到谷仓,尽可能多地睡觉,之后农民约翰醒来,早上挤奶。
贝西需要她的美丽睡眠,所以她想要尽快回来。
农民约翰的田地中有N(2 <= N <= 1000)个地标,唯一编号为1..N。
地标1是谷仓;
Bessie站在整个一天的苹果树丛是地标N.奶牛在田野中使用T(1 <= T <= 2000)两个不同长度的双向边让母牛在地标之间旅行。
Bessie对导航能力没有信心,所以她一开始就总是从一开始就停留下来。
鉴于地标之间的距离,确定贝西必须走路返回谷仓的最小距离。
保证有一些这样的路线存在。
输入
*行1:两个整数:T和N
*行2..T + 1:每行描述三个空格分隔的整数。
前两个整数是轨迹行进的地标。
第三个整数是路径的长度,范围为1..100。
产量
- 1号线:一个整数,Bessie必须旅行的距离从地标N到地标1的最小距离。
样品输入
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
样品输出
90
暗示
输入细节:
有五个地标。
输出详细信息:
Bessie可以通过跟踪路径4,3,2和1回家。
资源
[USACO 2004年11月
](http://poj.org/searchproblem?field=source&key=USACO+2004+November)
题目背景也是编的绕来绕去的,其实我们好好理解一下可以知道:
题意其实很简单 :就是给n个节点,m条无向边,求节点1到节点n的最短路径。
首先介绍一下spfa,其实这道题也可以用dijkstra来做,因为它没有出现负权变且数据范围足够,但是主要是为了练习一下spfa所以写一下。
spfa可以处理负权边,而且时间复杂度比dijkstra小,是个很实用的东西,其具体操作如下📄
首先定义一个队列q,先将起点s入队然后找到所有与s相连的点并用s来更新各个点的最短路径,也就是松弛操作,然后如果被更新的点在队列中就不管它,因为现在不管他以后也会管到它,如果不在队列中的就要把他塞进队列,还要对他进行更多的松弛操作,确保路径最短,然后最后队列为空就操作完毕
其代码如下也很好写
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,dis[1010],INF=9999999,vis[1010],f[1010][1010];
void BFS(int s){
queue<int>q;
for(int i=1;i<=n;i++) dis[i]=INF;
memset(vis,0,sizeof(vis));
q.push(s);
dis[s]=0;
vis[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
vis[x]=0;
for(int i=1;i<=n;i++){
if(dis[x]+f[x][i]<dis[i]&&f[x][i]!=INF){
dis[i]=dis[x]+f[x][i];
if(!vis[i]){
vis[i]=1;
q.push(i);
}
}
}
}
return ;
}
int main(){
cin>>m>>n;
int x,y,z;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)f[i][j]=0;
else f[i][j]=INF;
}
}
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
if(f[x][y]>z) f[x][y]=f[y][x]=z;
}
BFS(1);
cout<<dis[n]<<endl;
return 0;
}
网友评论