Xách valy về nước

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online Informatics Olympiad '09Day 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Kì thi lập trình sinh viên ACM ~-~ ICPC kết thúc cũng là lúc ktuanmicrosoft trở về Việt Nam ăn Noel. Sau khi gói gém xong đồ đạc, cả hai đồng ý với nhau sẽ đi MRT (Mass Rapid Transit, hệ thống xe điện ở Singapore) từ NTU ra sân bay Changi. Hai bạn quyết định mang đi một số đồng xu để trả tiền MRT, các đồng xu gồm nhiều mệnh giá khác nhau, mỗi mệnh giá bao gồm ~1~ số lượng đồng xu nhất định và thỏa mãn điều kiện:

  • Mỗi đồng xu có mệnh giá là một số nguyên dương
  • Tổng giá trị của tất cả các đồng xu là ~S~
  • Mọi số tiền trong đoạn ~1 \rightarrow S~ đều chỉ có duy nhất một cách dùng các đồng xu mang theo để trả. Ví dụ với ~S = 5~, những cách mang tiền đi là ~(1~, ~2~, ~2)~, ~(1~, ~1~, ~1~, ~1~, ~1)~ và ~(1~, ~1~, ~3)~. Những cách mang tiền không đúng ý của hai bạn là: ~(1~, ~1~, ~1~, ~2)~ vì số tiền ~2~ có thể trả bằng ~(1~, ~1)~ hoặc ~(2)~; số tiền ~3~ cũng có thể trả bằng ~(1~, ~1~, ~1)~ và ~(1~, ~2)~.

Trên đường đi hai bạn phải đi qua một số trạm (NTU và sân bay Changi cũng là trạm MRT), và để đi từ trạm này đến trạm khác hai bạn sẽ phải trả phí. Tuy nhiên cách thức thu phí ở Singapore cũng khá lạ đời. Nếu có chuyến MRT từ trạm ~X~ đến trạm ~Y~ thì phí của chuyến này là ~F_{XY}~, tuy nhiên bạn không cần phải trả số tiền ~F_{XY}~ mà phải chọn một loại mệnh giá xu bạn đang có trên tay sao cho còn lại đúng ~F_{XY}~ đồng xu mệnh giá này và trả hết số xu mệnh giá đó.

Yêu cầu: Không cho biết các mệnh giá xu và số lượng xu mang đi, hãy giúp hai bạn chọn các đồng xu thỏa mãn điều kiện ở trên và hai bạn có thể dùng các đồng xu này để có thể ra sân bay mà đi qua ít trạm MRT nhất. Hai bạn không muốn mang xu lên máy bay nên họ muốn sử dụng hết số xu mang đi.

Input

  • Dòng đầu tiên gồm ~5~ số tự nhiên ~N~, ~M~, ~s~, ~t~ và ~S~. Với ~N~ là số trạm MRT, ~M~ là số chuyến MRT giữa các trạm, ~s~ là chỉ số của NTU, ~t~ là chỉ số của sân bay Changi và ~S~ là tổng giá trị của số tiền hai bạn muốn mang đi.
  • ~M~ dòng tiếp theo, mỗi dòng gồm ~3~ số tự nhiên ~X~, ~Y~ và ~F_{XY}~. Có nghĩa là có chuyến MRT từ trạm ~X~ đến trạm ~Y~, và tất cả số đồng xu cùng loại phải trả trên chuyến này là ~F_{XY}~.

Output

  • Ghi ra một số duy nhất là số trạm MRT ít nhất các bạn cần phải đi qua để đi từ NTU đến sân bay hoặc ~- 1~ nếu không có cách nào cho hai bạn ra sân bay được với những yêu cầu oái oăm về xu của họ.

Giới hạn

  • ~2 \leq N \leq 1000~, ~1 \leq M \leq 10000~, ~1 \leq s, t\leq N~ và ~s\neq t~
  • ~1 \leq S \leq 10^{9}~
  • ~0 \leq F_{XY} \leq S~ với ~X \neq Y~

  • Có ~50\%~ số test thỏa mãn ~N \leq 100~.

Sample Input

4 5 1 4 5
1 2 1
1 3 2
2 4 2
3 4 1
1 4 5

Sample Output

2

Note

image

Có ~3~ cách mang xu thỏa mãn yêu cầu của hai bạn là: Cách ~1 (5~ đồng ~1~ xu) sẽ giúp hai bạn đi thẳng từ ~1 \rightarrow 4~. Cách ~2 (1~ đồng ~1~ xu, ~2~ đồng ~2~ xu) và cách ~3 (2~ đồng ~1~ xu và ~1~ đồng ~3~ xu) sẽ giúp hai bạn đi đường ~1 \rightarrow 2 \rightarrow 4~ hoặc ~1 \rightarrow 3 \rightarrow 4~. Đường đi ngắn nhất mà sử dụng hết xu là ~1 \rightarrow 4~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.