Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DHFRBUS - Vé xe miễn phí

Tham gia trò chơi nhảy lò cò, thật may mắn, Khuê đã giành giải nhất của cuộc thi. Phần thưởng mà Khuê nhận được là k vé xe buýt miễn phí để đi thăm quan thành phố Hạ Long. Mỗi vé xe chỉ được sử dụng một lần và có thể sử dụng cho bất kỳ tuyến xe buýt nào trong thành phố. Thành phố có n nút giao thông được đánh số từ 1 đến nm tuyến xe buýt hai chiều. Mỗi cặp nút giao thông i, j có không quá một tuyến xe buýt hai chiều, nếu có thì để đi từ nút i đến nút j (hoặc từ nút j đến nút i) với giá vé là cij = cji  đồng. Xuất phát từ nút giao thông s, Khuê muốn di chuyển đến nút giao thông t và anh luôn lựa chọn đường đi với chi phí ít nhất.

Ví dụ: thành phố có 5 nút giao thông và 6 tuyến xe buýt:

Tuyến 1: 1-2 giá vé 10 đồng; Tuyến 2: 2-5 giá vé 10 đồng;

Tuyến 3: 1-4 giá vé 3 đồng; Tuyến 4: 3-4 giá vé 5 đồng;

Tuyến 5: 3-5 giá vé 3 đồng; Tuyến 6: 1-3 giá vé 20 đồng.

 

 

Xuất phát từ nút 1 đến nút 5, đi theo hành trình 1à4à3à5 hết 11 đồng là đường đi với chi phí ít nhất. Tuy nhiên, nếu Khuê sử dụng 1 vé xe miễn phí thì đường đi 1à3à5 hết 3 đồng là ít nhất (vé xe miễn phí được sử dụng tại tuyến 1-3).

Yêu cầu: Cho biết các tuyến xe buýt với giá vé tương ứng và các giá trị s, t, k. Hãy tính chi phí ít nhất để đi từ nút giao thông s đến nút giao thông t mà không sử dụng quá k vé xe miễn phí.

 

Input

-          Dòng đầu tiên ghi năm số nguyên dương n, m, k, s, t; 

-          m dòng sau, mỗi dòng 3 số nguyên i, j, cij mô tả có tuyến xe buýt i – j hết cij đồng.

Output

một số duy nhất là chi phí ít nhất để đi từ nút giao thông s đến nút giao thông t mà không sử dụng quá k vé xe miễn phí.

Example

Input:

5 6 1 1 5

1 2 10

2 5 10

1 4 3

3 4 5

3 5 3

1 3 20 Output: 3

Ghi chú:

  • Có 40% số test ứng với 40% số điểm có n ≤ 100, m ≤ 1000 và k = 1;
  • Có 20% số test ứng với 20% số điểm có n ≤ 105, m ≤ 105k = 1;
  • Có 40% số test còn lại ứng với 40% số điểm có n ≤ 105, m ≤ 105 k ≤ 5.

Được gửi lên bởi:VOJ Team
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED

hide comments
2019-04-06 10:30:31
long long to AC :V
2018-08-15 16:47:55
Khủng =))
2018-06-18 04:34:51
nhật hào sạch
2018-05-30 04:45:46
trau cung AC ez vcl
2017-10-31 16:53:19
Bellman - Ford cũng AC
2017-07-20 05:08:50
??? :D ???
2017-05-04 11:48:53
Bạn nào làm bài này chú ý là c[i,j] vượt longint nhé.
2017-03-02 17:57:52
:D 97.14 ?
2017-02-08 14:58:10
đề nghị mấy bạn duyệt trâu cũng AC bớt cmt spam nhé :)) k phải cái gì cũng đùa được đâu :)) lúc bị ban nick lại kêu
2016-06-02 12:31:03
đã AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.