CSES2121 包裹递送
#CS2121. 包裹递送
包裹递送
题目背景
翻译自 CSES-2121 题。
题目描述
有n个城市和m条路线，通过这些路线，包裹可以从一个城市运送到另一个城市。对于每条路线，你知道最大可以运输的包裹数和每个包裹的运费。
你需要将k个包裹从Syrjälä（城市1）送到Lehmälä（城市n）。请你找出最便宜的运输方式。
输入格式
第一行包含三个整数n、m和k：分别表示城市数、路线数和包裹数。城市编号从1到n，城市1是Syrjälä，城市n是Lehmälä。
接下来有m行，每行描述一条路线。每行包含四个整数a、b、r和c，表示从城市a到城市b有一条路线，最多可以运输r个包裹，每个包裹的费用是c。
输出格式
输出一个整数：最小的总费用，如果没有解，则输出−1-1−1。
样例
4 5 3
1 2 5 100
1 3 10 50
1 4 7 500
2 4 8 350
3 4 2 100
750
样例1解释
-
通过路线1→2→41→2→41→2→4（1个包裹，费用1×450=4501 \times 450 = 4501×450=450）运送1个包裹。
-
通过路线1→3→41→3→41→3→4（2个包裹，费用2×150=3002 \times 150 = 3002×150=300）运送2个包裹。
-
总费用为450+300=750450 + 300 = 750450+300=750。
说明/提示