6968. 邮包配送 (Parcel Delivery)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 共有 $n$ 个城市和 $m$ 条有向运输路线。你可以通过这些路线将包裹从一个城市运送到另一个城市。对于每条路线，已知其运送包裹的数量上限（容量限制）以及运送单个包裹所需的费用。 你希望从城市 $1$（Syrjälä）运送 $k$ 个包裹到城市 $n$（Lehmälä）。请问最便宜的运送方案所需的花费是多少？ ## 输入格式 第一行包含三个整数 $n, m$ 和 $k$，分别表示城市数量、运输路线数量和包裹数量。城市编号为 $1, 2, \dots, n$。 接下来 $m$ 行描述这些运输路线。每行包含四个整数 $a, b, r$ 和 $c$，表示存在一条从城市 $a$ 指向城市 $b$ 的单向路线，其容量上限为 $r$ 个包裹，且每个包裹的运送单价为 $c$。 ## 输出格式 输出一个整数，表示运送所有包裹的最小总费用。如果无解（即无法成功运送 $k$ 个包裹），则输出 `-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 ``` ### 输出 #1 ``` 750 ``` ### 样例解释 分配方案如下： * 有 $1$ 个包裹通过路线 $1 \rightarrow 2 \rightarrow 4$ 运送（费用为 $1 \cdot (100 + 350) = 450$）。 * 有 $2$ 个包裹通过路线 $1 \rightarrow 3 \rightarrow 4$ 运送（费用为 $2 \cdot (50 + 100) = 300$）。 总花费为 $450 + 300 = 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$