1332_分道扬镳

编号为1…N 的N个城市之间以单向路连接，每一条道路有两个参数：路的长度和通过这条路需付的费用。

Bob和Alice生活在城市1，但是当Bob发现了Alice玩扑克时欺骗他之后，他决定与她翻脸，离开城市1前往城市N。Bob想尽快到达城市N，但是他的钱不多。

希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。

输入的第一行是3个整数 K, N, R ，其中：

    K：表示Bob能承受的最大费用，0 ≤ K ≤ 10000

    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

为每个测试用例输出一行结果：总费用小于或等于最大费用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

测试数据的图中可能有重边、有自环。

这题有一定难度，但学完DFS和BFS就要能够AC它。它是一道典型的搜索题，而且需要强剪枝（去掉 当前已知无效的搜索路径），以便加快搜索速度。