CSES 2121 - 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\)。

範例輸入 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 \rightarrow 2 \rightarrow 4\)（費用 \(1 \cdot 450 = 450\)），兩個包裹走路線 \(1 \rightarrow 3 \rightarrow 4\)（費用 \(2 \cdot 150 = 300\)）。

限制

• \(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\)

題目來源

CSES - Parcel Delivery

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。