PKU POJ 1724 ROADS 解题报告

看来我的搜索真的很烂,简单的搜索都搞定的这么痛苦

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

题目大意是输入 拥有钱数,城市数,路的数量

然后输入格式是 起点,终点,路长,路费

要求从城市1到城市n的路费不超过拥有的钱的最短路

就是有条件的最短路问题

我的方法就是BFS搜索

减枝的地方很简单,就是路费超过拥有的费用就跳过,记录状态时候可以用堆或者优先队列如图:

如果路的输入是

1 2 3 0
1 3 2 0
1 4 5 0
3 4 9 0
2 4 1 0

那么BFS的结果就是(带括号的为到终点的路长)

第一层1->2,1->3,1->4,记录的状态就是路长分别为:3,2,5,队列为:2,3,(5)

第二层3->4,队列为:3,(5),(11)

第三层2->4,队列为:(4),(5),(11)

由于最短路径是到终点的,所以跳出,4就是答案

贴代码:

/**
 * URL:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724
 * Author: OWenT
 * 优先队列(STL)+BFS
 */
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define inf 1000000

class node
{
public:
    long pdl, d, ctm;//已走过的路长, 终点, 花费
    friend bool operator<(node a,node b)
    {
       return a.pdl > b.pdl;
    }
};

typedef struct
{
    long d,l,t;
}road;

vector<road>rd[10005];//路
priority_queue<node>state;//STL 优先队列
int main()
{
    long k,n,r,i,output = inf;
    scanf("%ld %ld %ld", &k, &n, &r);

    for(i = 0; i < r; i ++)
    {
        road tmpRd;
        long s;
        scanf("%ld %ld %ld %ld", &s, &tmpRd.d, &tmpRd.l, &tmpRd.t);
        rd[s].push_back(tmpRd);
    }

    //初始化
    node tmpNd;
    tmpNd.ctm = tmpNd.pdl = 0;
    tmpNd.d = 1;
    state.push(tmpNd);

    //BFS
    while(!state.empty())
    {
        node nd = state.top();
        state.pop();
        long s = nd.d;
        if(s == n)
        {
            output = nd.pdl;
            break;
        }
        for(i = 0; i < rd[s].size(); i ++)
        {
            if(nd.ctm + rd[s][i].t <= k)
            {
                node ad;
                ad.d = rd[s][i].d;
                ad.ctm = nd.ctm + rd[s][i].t;
                ad.pdl = nd.pdl + rd[s][i].l;
                state.push(ad);
            }
        }
    }

    //输出,inf即为没有符合的情况
    if(output >= inf)
        printf("-1\n");
    else
        printf("%ld\n", output);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之最大子向量和(连续子数组的最大和)(九度OJ1372)

题目描述: HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天JOBDU测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和...

21210
来自专栏数据小魔方

IF函数——放松工作,享受生活!

今天跟大家分享一个简单却实用、高效的逻辑函数——IF函数。 ▼ IF函数可以简化很多我们数据处理过程中的重复性操作工作,让我们的工作效率大大提高。今天通过两个例...

3225
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习_二分查找算法

2194
来自专栏用户2442861的专栏

2014美团网笔试题目(总结)

http://blog.csdn.net/wzy_1988/article/details/12438143

1751
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

4196
来自专栏PPV课数据科学社区

【学习】笨办法学R编程(二)

经历了前面两个小挑战,你应该对R有点理解了。我们继续推进,今天的问题有点点复杂,复杂的不是R,而是一个数学概念:质数和质因子。任何一个合数都可以...

3099
来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

2105
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

3135
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

1801
来自专栏灯塔大数据

解密 | 一文总结学习 Python 的 14 张思维导图

前言 本文主要涵盖了 Python 编程的核心知识(暂不包括标准库及第三方库,后续会发布相应专题的文章)。 首先,按顺序依次展示了以下内容的一系列思维导图:基础...

3537

扫码关注云+社区

领取腾讯云代金券