> For the complete documentation index, see [llms.txt](https://blog.owent.net/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.owent.net/2010/50.md).

# 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就是答案

贴代码：

```cpp
/**
 * 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;
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://blog.owent.net/2010/50.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.