poj1724ROADS(BFS)

时间:2021-11-22 12:12:22

链接

本来想写spfa 加点什么限制什么的可能就过了 写着写着就成裸BFS了 也没优化就水过了

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
#define N 110
#define M 10010
#define INF 0xfffffff
struct node
{
int u,v,w,next,len;
}ed[M<<];
struct mode
{
int u,sum,len;
};
int head[N],vis[N],dis[N];
int n,m,t,sp,ans;
void init()
{
t = ;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w,int len)
{
ed[t].u = u;
ed[t].v = v;
ed[t].w = w;
ed[t].len = len;
ed[t].next = head[u];
head[u] = t++;
}
void spfa()
{
queue<mode>q;
mode ss,st;
int i;
for(i = ; i <= n ; i++)
dis[i] = INF;
ss.u = ;
ss.sum = ;
ss.len = ;
q.push(ss);
dis[] = ;
while(!q.empty())
{
ss = q.front();
q.pop();
int u = ss.u;
if(ss.len>ans)
continue;
if(u==n)
{
ans = ss.len;
continue;
}
for(i = head[u] ; i!=- ; i = ed[i].next)
{
int v = ed[i].v;
if(ss.sum+ed[i].w<=sp)
{
st.len = ss.len+ed[i].len;
st.u = v;
st.sum = ss.sum+ed[i].w;
q.push(st);
}
}
}
if(ans!=INF)
printf("%d\n",ans);
else
printf("-1\n");
}
int main()
{
int i,u,v,len,w;
while(scanf("%d",&sp)!=EOF)
{
init();
ans = INF;
scanf("%d%d",&n,&m);
for(i = ; i <= m ;i++)
{
scanf("%d%d%d%d",&u,&v,&len,&w);
add(u,v,w,len);
}
spfa();
}
return ;
}

poj1724ROADS(BFS)的更多相关文章

  1. 深搜(DFS)广搜(BFS)详解

    图的深搜与广搜 一.介绍: p { margin-bottom: 0.25cm; direction: ltr; line-height: 120%; text-align: justify; orp ...

  2. 【算法导论】图的广度优先搜索遍历(BFS)

    图的存储方法:邻接矩阵.邻接表 例如:有一个图如下所示(该图也作为程序的实例): 则上图用邻接矩阵可以表示为: 用邻接表可以表示如下: 邻接矩阵可以很容易的用二维数组表示,下面主要看看怎样构成邻接表: ...

  3. 深度优先搜索(DFS)与广度优先搜索(BFS)的Java实现

    1.基础部分 在图中实现最基本的操作之一就是搜索从一个指定顶点可以到达哪些顶点,比如从武汉出发的高铁可以到达哪些城市,一些城市可以直达,一些城市不能直达.现在有一份全国高铁模拟图,要从某个城市(顶点) ...

  4. 【BZOJ5492】&lbrack;HNOI2019&rsqb;校园旅行(bfs)

    [HNOI2019]校园旅行(bfs) 题面 洛谷 题解 首先考虑暴力做法怎么做. 把所有可行的二元组全部丢进队列里,每次两个点分别向两侧拓展一个同色点,然后更新可行的情况. 这样子的复杂度是\(O( ...

  5. 深度优先搜索(DFS)和广度优先搜索(BFS)

    深度优先搜索(DFS) 广度优先搜索(BFS) 1.介绍 广度优先搜索(BFS)是图的另一种遍历方式,与DFS相对,是以广度优先进行搜索.简言之就是先访问图的顶点,然后广度优先访问其邻接点,然后再依次 ...

  6. 图的 储存 深度优先(DFS)广度优先(BFS)遍历

    图遍历的概念: 从图中某顶点出发访遍图中每个顶点,且每个顶点仅访问一次,此过程称为图的遍历(Traversing Graph).图的遍历算法是求解图的连通性问题.拓扑排序和求关键路径等算法的基础.图的 ...

  7. 数据结构与算法之PHP用邻接表、邻接矩阵实现图的广度优先遍历(BFS)

    一.基本思想 1)从图中的某个顶点V出发访问并记录: 2)依次访问V的所有邻接顶点: 3)分别从这些邻接点出发,依次访问它们的未被访问过的邻接点,直到图中所有已被访问过的顶点的邻接点都被访问到. 4) ...

  8. 层层递进——宽度优先搜索(BFS)

    问题引入 我们接着上次“解救小哈”的问题继续探索,不过这次是用宽度优先搜索(BFS). 注:问题来源可以点击这里 http://www.cnblogs.com/OctoptusLian/p/74296 ...

  9. HDU&period;2612 Find a way (BFS)

    HDU.2612 Find a way (BFS) 题意分析 圣诞节要到了,坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车.百度地图一下,发现周围的召唤师大峡谷还不少,这对基佬纠结着,该去哪一个...坤 ...

随机推荐

  1. thinkphp 3&period;23语言包加载

    模块home: 1.config 里添加 配置 //'配置项'=>'配置值'    'LANG_SWITCH_ON'   => true,      // 开启语言包功能    'LANG ...

  2. BAT齐聚阿里安全-ASRC生态大会:呼吁联合共建网络安全白色产业链

    图说:近日,阿里安全-ASRC生态大会在杭州举行,包括BAT在内的20余家国内知名互联网企业代表,回顾过去一年网络安全面临的问题与挑战,共谋生态安全治理思路. "123456.111111. ...

  3. Win10 安装 VMWare中 MAC OS X的安装,VMWare tools的配置与iOS的Helloworld

    iOS的开发必须在MAC OS X系统下进行,这很蛋疼,现在MACBOOK动不动就上千上万大洋,这足够买台配置怪兽了,好吗?然而,我们是可以通过在VMWare中安装MAC OS X进行iOS开发的.对 ...

  4. 系统学习PHP的一些思路

    作为一名新进的PHPer,迫切的想提高自己的编码水平,目前市面上几乎没有高手来给新手指点出一条相对靠谱的途径. 首先,面对PHP众多杂乱无章的各种函数,到底该怎么去理清其各者之间的关系,经过一段时间的 ...

  5. django-celery 创建多个broker队列 异步执行任务时指定队列

    一.这里不再详细述说 django 框架中如何使用celery, 重点放在如何实现创建多个队列, 并指定队列存放异步任务 笔者使用   django-celery==3.2.2 模块, 配置项及配置参 ...

  6. CentOS 6 安装python3&period;6

    参考博客:https://www.cnblogs.com/xiaodangshan/p/7197563.html 安装过程比较简单,需要注意,安装之后,为了不影响系统自带的python2.6版本,需要 ...

  7. (转)Elasticsearch NoNodeAvailableException None of the configured nodes are available

    问题背景:将es部署到内网中两台服务器,其Ip地址分别为:192.111.222.5,192.111.222.1(部署方式完全一样,是将192.111.222.1服务器上es整个部署包,拷贝到了192 ...

  8. easyui常用属性

    属性分为CSS片段和JS片段. CSS类定义:1.div easyui-window        生成一个window窗口样式.      属性如下:                   1)mod ...

  9. mongo操作及相关资料

    mongo操作 find方法 db.collection_name.find(); 查询所有的结果: select * from users; db.users.find(); 指定返回那些列(键): ...

  10. 关闭TCP中135、139、445、593、1025 等端口的操作方法 &lpar;转&rpar;(记录下)

    操作要领:封闭端口,杜绝网络病毒对这些端口的访问权,以保障计算机安全,减少病毒对上网速度的影响. 近日发现有些人感染了新的网络蠕虫病毒,该病毒使用冲击波病毒专杀工具无法杀除,请各位尽快升级计算机上的杀 ...