美文网首页Noip算法之图论
poj2387 (spfa模板)

poj2387 (spfa模板)

作者: 不给赞就别想跑哼 | 来源:发表于2017-10-04 16:37 被阅读19次

把母牛带回家

**时间限制:

** 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;
} 

相关文章

  • poj2387 (spfa模板)

    把母牛带回家 **时间限制: ** 1000MS **内存限制: ** 65536K **总提交: ** 5946...

  • ——Bellman-Ford

    初始状态: 模板:1 模板2:FIFO队列优化 Spfa是Bellman-Ford算法利用队列的优化,Bellma...

  • 算法模板(三)最短路问题

    Dijkstra SPFA Floyd

  • 最短路径模板

    堆优化的Dijkstra 普通Dijkstra SPFA

  • 算法实现-SPFA

    参考:最短路径问题---SPFA算法详解

  • Extended Traffic LightOJ - 1074

    题意:求最短路 权为差的立方及存在负权思路: spfa_dfs 判负权 + spfa_bfs 求最短路 TLE s...

  • SPFA算法

    输出

  • SPFA研究

    说起来,SPFA这个算法之前一直是半懂不懂,偶尔敲一个模板,然后囫囵做个两三道水题,倒也是轻松,然而一旦遇到比较复...

  • 图-2

    spfa算法 spfa的思路异常地顺(可能是因为我之前写错的dijkstra有一点相似),简直就是bfs的翻版。做...

  • 终于刷完了——PAT甲级-1131. Subway Map (3

    题意不说了,有特殊要求的最短路。对于单源最短路,我是无脑上SPFA,SPFA也写了不下十遍,然而这次没有处理好。关...

网友评论

    本文标题:poj2387 (spfa模板)

    本文链接:https://www.haomeiwen.com/subject/mhdcyxtx.html