2016年2月24日 星期三

[HOJ 190]攻略路徑 (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 190 - 攻略路徑

Problem Statistics
Solved Member: 16  Submission: 152  User Tried: 19
Problem:
如你所知,瀚瀚是一個大忙人。

每天每天,他有很多的 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:
本題有多筆測資,請讀到 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:
2 2 3 1
1 2 1
2 1 1

3 3 10 1
1 2 1
2 3 1
3 1 1
Sample Output:
2
9
HINT:
30% 的測資滿足: n ≤ 10 且 m ≤ 30 且 k ≤ 1000
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
05000ms65536kb
15000ms65536kb10
25000ms65536kb10
35000ms65536kb10
45000ms65536kb10
55000ms65536kb10
65000ms65536kb10
75000ms65536kb10
8-15000ms65536kb10
8-25000ms65534kb
9-15000ms65536kb10
9-25000ms65534kb
10-15000ms65536kb10
10-25000ms65534kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原