焼肉

ブログに記事を書きます Advent Calendar 2014 - Adventarの14日目です。

notさんの焼肉チャレンジ。
前回のARCの師匠のD問題のgreedyを落とします。
下をドラッグすると見えます。解説とかも見えます。

4 5
100 10 10 10
10 1 1 1 45
1 5
2 1 2
2 1 3
2 1 4

takayuta: 2.24137931
正答: 30/13

詳しいこと

グラフだと思いました。
tはアイテムたち。辺が経験値です。t5は自己辺があると思ってください。
t3
l
l
t1---t2
l
l
t4

t5
で、正答がt1-t2,t3,t4の3辺をとるとき、師匠のgreedyだとかならず途中でt5を使うようにうまくコストを設定します。