Parcel Delivery

题目描述

有 n 个城市和 m 条可以将包裹从一个城市运送到另一个城市的路线。对于每条路线，你知道最大可运送的包裹数量和单个包裹的费用。 你想把 k 个包裹从 Syrjälä 发送到 Lehmälä。最便宜的方法是什么？

输入格式

第一行输入包含三个整数 n、m 和 k：城市数量、路线数量和包裹数量。城市编号为 1,2,\dots,n。城市 1 是 Syrjälä，城市 n 是 Lehmälä。 接下来有 m 行描述这些路线。每行有四个整数 a、b、r 和 c：存在一条从城市 a 到城市 b 的路线，最多可通过该路线运送 r 个包裹，且每个包裹的费用为 c。

输出格式

输出一个整数：最小总费用，若无可行方案则输出 -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

提示

$2 \le n \le 500$ $1 \le m \le 1000$ $1 \le k \le 100$ $1 \le a,b \le n$ $1 \le r,c \le 1000$ 样例解释：一个包裹通过路线 1 \rightarrow 2 \rightarrow 4 运输（费用 1 \cdot 450=450），两个包裹通过路线 1 \rightarrow 3 \rightarrow 4 运输（费用 2 \cdot 150=300）。

标签: CSES2121|先进技术

来源

CSES2121|先进技术