Pro.ID1332 Title分道扬镳 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1332 AC138 Submit883 Ratio15.63% 时间&空间限制描述编号为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 输出Description 编号为1…N 的N个城市之间以单向路连接,每一条道路有两个参数:路的长度和通过这条路需付的费用。 Bob和Alice生活在城市1,但是当Bob发现了Alice玩扑克时欺骗他之后,他决定与她翻脸,离开城市1前往城市N。Bob想尽快到达城市N,但是他的钱不多。 希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。 Input 输入的第一行是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 Output 为每个测试用例输出一行结果:总费用小于或等于最大费用K的最短路径的长度。如果这样的路径不存在,则仅仅输出 -1 。 Sample Input 5 6 7 Sample Output 11 Hint 测试数据的图中可能有重边、有自环。 这题有一定难度,但学完DFS和BFS就要能够AC它。它是一道典型的搜索题,而且需要强剪枝(去掉 当前已知无效的搜索路径),以便加快搜索速度。 样例输入5 6 7 样例输出11 提示测试数据的图中可能有重边、有自环。 这题有一定难度,但学完DFS和BFS就要能够AC它。它是一道典型的搜索题,而且需要强剪枝(去掉 当前已知无效的搜索路径),以便加快搜索速度。 作者 |