用c++做下面这道题目。题目描述： N个以1 ... N标号的城市通过单向的道路相连。每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）。 Bob和Alice过去住在城市1。在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后，Bob和她分手了，并且决定搬到城市N。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径，前提是他能够付的起通行费。 输入描述： 第一行包含一个整数K，0<=K<=10000，代表Bob能够在他路上花费的最大的金币数。第二行包含整数N，2<=N<=100，指城市的数目。第三行包含整数R，1<=R<=10000，指路的数目。接下来的R行，每行具体指定几个整数S, D, L和T，来说明关于道路的一些情况，这些整数之间通过空格间隔，其中S是道路起始城市，1 <= S <= N，D是道路终点城市，1<=D <=N，L是道路长度，1<=L<=100，T是通行费(以金币数量形式度量)，0<=T<=100。注意不同的道路可能有相同的起点和终点。 输出描述： 输出结果应该只包括一行，即从城市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

这是一道经典的最短路问题，可以使用 Dijkstra 算法或者 Bellman-Ford 算法来解决。这里我使用 Dijkstra 算法。

首先，我们需要用一个邻接表来存储图。对于每个城市，我们可以用一个链表来存储它所能到达的城市及对应的道路长度和通行费。然后，我们可以使用一个数组来记录从城市1到每个城市的最短路径长度，初始值为无穷大。同时，我们还需要使用一个小根堆来存储当前可达的城市及对应的最短路径长度，初始时只有城市1在堆中，路径长度为0。

接下来，我们每次从堆中取出路径长度最短的城市，更新其可达的城市的最短路径长度，并将这些城市加入堆中。具体地，对于每个可达城市，如果从当前城市到该城市的路径长度加上通行费小于等于K，并且该路径长度加上当前城市的最短路径长度小于该城市的最短路径长度，则更新该城市的最短路径长度，并将其加入堆中。

最后，如果城市N的最短路径长度小于无穷大，则输出该长度，否则输出-1。

下面是代码实现：