N - Waterway Dungeon
問題文
$N$ 個の部屋と $M$ 本の水路からなるダンジョンがあります。部屋には $1$ から $N$ までの番号が、水路には $1$ から $M$ までの番号が付けられています。水路 $i$ は部屋 $u_i$ と部屋 $v_i$ を結んでおり、通過すると $w_i$ の魔力を得ます。ここで、$w_i$ は負の値になることもあります。
はじめ、あなたの体力は $L$、魔力は $0$ です。水路を $1$ 回通過するごとに体力を $1$ 消費します。体力が $0$ 未満になる移動を行うことはできません。
初期状態ではすべての水路の水は静止しており、双方向に通行可能です。しかし、一度水路を通過すると、進んだ方向に強い水流が発生します。以降、その水路は水流の方向にのみ通行可能となり、逆方向に通行することはできません。
あなたは部屋 $1$ から出発します。同じ部屋や水路を複数回通ることも可能ですが、水流に逆らって進むことはできません。部屋 $N$ はボス部屋への入口であり、部屋 $N$ にいるときはいつでもボス部屋へ入ることができます。ボス部屋へ入ったら二度とダンジョンに戻ることはできません。
ボス部屋へ入った時点で得ている魔力の合計の最大値を求めてください。
制約
- $2 \le N \le 100$
- $N - 1 \le M \le \min\left( 300, \dfrac{N (N-1)}{2} \right)$
- $1 \le L \le 9$
- $|w_i| \le 10^{9}$
- $1 \le u_i, v_i \le N$
- $u_i \ne v_i$
- $i \ne j \implies \lbrace u_i, v_i \rbrace \ne \lbrace u_j, v_j \rbrace$
- 部屋 $1$ から部屋 $N$ へ至る、通る水路の本数が $L$ 以下の経路が存在する
- 入力はすべて整数
部分点
上記の制約に加えて以下の制約を満たすテストケースすべてに正解した場合、部分点として 20 点が与えられる。
- $N \le 11$
- $L \le 7$
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$ $L$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$
出力
ボス部屋へ入った時点で得ている魔力の合計の最大値を整数で出力してください。
4 5 7
1 2 4
1 3 -4
2 3 -3
2 4 -1
3 4 5
7
部屋を $1 \to 2 \to 3 \to 4 \to 2 \to 3 \to 4$ の順に進んでボス部屋へ入ることで、魔力を $4 + (-3) + 5 + (-1) + (-3) + 5 = 7$ 得ることができます。$8$ 以上の魔力を得てボス部屋へ入ることはできないため、$7$ を出力してください。
例えば、$1 \to 2 \to 4 \to 3 \to 2 \to 1 \to 3 \to 4$ の順に進むことができれば魔力を $10$ 得ることができますが、部屋 $1$ から部屋 $2$ に通行した後は水流が発生して部屋 $2$ から部屋 $1$ へ通行することはできなくなるため、この経路は通行できません。
この入力例は部分点の制約を満たします。
6 11 7
1 2 10
1 3 3
1 4 3
1 5 1
1 6 -7
2 3 -2
2 4 -1
2 5 1
2 6 -5
3 4 3
5 6 4
30
部屋を $1 \to 2 \to 4 \to 3 \to 1 \to 2 \to 5 \to 6$ の順に進んでボス部屋へ入ることで、魔力を $10 + (-1) + 3 + 3 + 10 + 1 + 4 = 30$ 得ることができます。$31$ 以上の魔力を得ることはできないため、$30$ を出力してください。
この入力例は部分点の制約を満たします。
8 7 5
5 6 70
2 4 80
7 8 40
4 5 -30
3 4 20
5 8 60
1 4 50
80
必ずしもボス部屋へ入るまでに体力を $0$ まで使い切る必要はありません。
この入力例は部分点の制約を満たします。
9 14 9
5 6 1000000000
5 1 -61088967
6 3 69075471
1 7 -28544946
5 8 -16127931
8 2 -63029924
7 4 -62867813
8 9 1000000000
2 6 49233086
2 3 37665626
2 5 53734394
6 8 85609638
1 9 1000000000
3 4 55467959
5127488151
答えは 32 bit 整数に収まらないことがあります。
この入力例は部分点の制約を満たしません。