Problem : 190 - 攻略路徑

Problem Statistics

Solved Member: 16　　Submission: 152　　User Tried: 19

Statement:

如你所知，瀚瀚是一個大忙人。

每天每天，他有很多的 game 以及蘿莉需要攻略，近日瀚瀚正在破一款名為戀愛蠟筆的鬼畜ゲー，這遊戲是出了名的複雜，有 N 隻可以攻略的蘿莉，並且有 M 個不同的 flag 事件。我們暫且將蘿莉由 1 編號到 N，並把 flag 由 1 編號到 M。

每個時刻會有一隻目前好感度最高的蘿莉作為目前的主線，在某些主線中有特定的 flag 可以觸發而改變目前的主線。但是觸發 flag 是有難度的，每個 flag i 都有他觸發的難度值 Wi。

假設瀚瀚玩遊戲的順序分別為： L1, F1, L2, F2, ... ,Ft, Lt+1
其中 L1~Lt+1 分別代表每次進入的主線(有可能重複攻略)，而 F1~Ft 為每次所經過的 flag，則這條路線攻略的難度可表示為 WF1 + WF2 + ... + WFt。

瀚瀚覺得這遊戲太簡單了，希望能找一條難度第 k 小的攻略路線來玩，請你告訴他難度第 k 小的攻略路徑有多難。
路線 L1, F1, ... , Fi, Li+1 以及路線 L'1, F'1, ... , F'j, L'j+1 不同代表其中至少有任意一個數字是不相同的。

Input:Output:

本題有多筆測資，請讀到 EOF 為止。
每筆測資第一行有 4 個整數 N,M,k,s，分別代表蘿莉個數、flag個數、瀚瀚想找第 k 小的攻略路徑、以及最剛開始在蘿莉 s 的主線。
接下來有 M 行，每行包刮三個整數 Ai,Bi,Wi，代表在主線 Ai 會觸發一個到主線 Bi 的 flag，困難度為 Wi。

其中：
N ≤ 100000
M ≤ 500000
0 ≤ Wi ≤ 1000
1 ≤ k ≤ 100000

可以假設答案一定存在

Sample Input:Sample Output:

2 2 3 1
1 2 1
2 1 1

3 3 10 1
1 2 1
2 3 1
3 1 1

2
9

HINT:

30% 的測資滿足: n ≤ 10 且 m ≤ 30 且 k ≤ 1000

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	5000ms	65536kb
1	5000ms	65536kb	10
2	5000ms	65536kb	10
3	5000ms	65536kb	10
4	5000ms	65536kb	10
5	5000ms	65536kb	10
6	5000ms	65536kb	10
7	5000ms	65536kb	10
8-1	5000ms	65536kb	10
8-2	5000ms	65534kb
9-1	5000ms	65536kb	10
9-2	5000ms	65534kb
10-1	5000ms	65536kb	10
10-2	5000ms	65534kb