此题不会做（C++给代码）

Question

描述
现在有N个城市，编号分别为1到N，他们之间用单向道路进行相连。值得注意的是，每条道路有2个参数：道路长度和需要为此道路支付的通行费。

现在周末来了，住在城市1的小明，拿上了他的钱包和他的switch，准备和小红一起玩1小时游戏。但是小红住在城市N，且小明的零花钱有限。

需要聪明的你帮助小明找到从城市1到城市N的最短路径，而且他能付得起这个通行费。

输入格式
第1行输入K。 这是小明拥有的零花钱K元。

第2行输入N。这是城市总数N。

第3行输入M。这是城市之间的单向道路数。

接下来的M行，每行输入一道道路，道路信息包含4个数字，分别代表每条道路的4个信息：S, D, L, C。

S为道路的起点（城市编号），D为道路终点（城市编号）， L为该道路的长度，C为该道路的通行费。

依次类推，输入若干组样例。



输出格式
第1行输出第1个样例的结果，1个数字。代表小明从城市1到城市N的最短路径，该路径通行费小于等于K。如果不存在这样的最短路输出-1。

依次类推，输出其他组样例的结果。

输入样例
5

6

7

1 2 2 3

2 4 3 3

3 4 2 4

1 3 4 1

4 6 2 1

3 5 2 0

5 4 3 2

输出样例
11

数据范围
0 <= K <= 10000,

2 <= N <= 100,

1 <= M <= 10000,

Answer 1

这个是路径规划问题，可以参考一下：https://blog.csdn.net/YF_Li123/article/details/74090301
如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，谢谢