链接: https://cses.fi/problemset/task/2121

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $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$。

数据范围

$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$

样例输入

4 5 3
1 2 5 100
1 3 10 50
1 4 7 500
2 4 8 350
3 4 2 100

样例输出

750