# PKU POJ 1724 ROADS 解题报告

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

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

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 ++)
{
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)
{
}
}
}

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

167 篇文章28 人订阅

0 条评论

## 相关文章

21210

3225

2194

### 2014美团网笔试题目（总结）

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

1751

4196

3099

2105

### 矩阵快速幂小结

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

3135

1801

3537