221 . 逃脫大戰
TopCoder
Tags
Description
現在你在一個國家，這個國家有 $N$ 個城鎮，編號為 $1, 2, \dots, N$ 。
現在，有 $K$ 個人要從城鎮 $1$ 出發，逃離到城鎮 $N$ 。他們可以藉由 $M$ 條道路來逃離。第 $i$ 條單向路可以讓那些人從城鎮 $u_i$ 到城鎮 $v_i$ 。但是，第 $i$ 條路只能讓 $f_i$ 個人經過，並且每當一個人經過時，需要徵收 $c_i$ 塊過路費。
除此之外，每個城鎮也有容量上限。第 $i$ 個城鎮最多只能讓 $w_i$ 個人經過。
現在，請問最多有多少人可以成功停在城鎮 $N$ ，以及在這個情況下，最小需要繳交多少過路費。
注意 Hint 有帥哥總召送給大家的東西（？）
Input Format
輸入的第一行包含三個整數 $N, M, K$ ，代表城鎮個數、邊的個數，以及人數。
接下來的一行，包含 $N$ 個整數 $w_1, w_2, \dots, w_N$ 。$w_i$ 代表城鎮 $i$ 可以被經過的人數。
接下來的 $M$ 行，每行包含四個整數 $u_i, v_i, c_i, f_i$ ，意義已經在題目敘述中敘述過了。
- $2 \leq N \leq 100$
- $0 \leq M \leq 100$
- $1 \leq K \leq 100$
- $1 \leq u_i, v_i \leq N$
- $1 \leq c_i, f_i \leq 100$
Output Format
輸出兩個整數於一行。第一個整數代表最多有多少人可以停在城鎮 $N$ ，以及在這個情況下，最少要花多少過路費。
Sample Input 1
3 4 4
5 5 5
1 2 3 5
1 2 2 2
2 3 3 1
1 3 2 6
5 5 5
1 2 3 5
1 2 2 2
2 3 3 1
1 3 2 6
Sample Output 1
4 18
Hints
有一天，你撿到了一張報紙，報紙內容如下：
「
最後的個人賽
小明超級厲害
花了兩個小時
費氏數列ＡＣ
最後的個人賽
大明有點品祥
流水題不ＡＣ
」
Problem Source
IOICamp 2021 Day4 pE
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~15 | 無額外限制 | 100 |