問題一覧 > 通常問題

No.2712 Play more!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 91
作問者 : 👑 Nafmo2Nafmo2 / テスター : dyktr_06dyktr_06 sepa38sepa38 ryota2357ryota2357
0 ProblemId : 9989 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-31 14:20:04

問題文

Nafmoくんは,$N$ 個 のダンジョンからなるゲームをこれから始めようとしています.
ダンジョンにはそれぞれ $1$ から $N$の番号が振られており,ダンジョン $i (1 \leq i \leq N)$ は攻略に $A_i$ 時間かかります.
また,ダンジョン間を結ぶ一方通行の道が $M$ 本 あり,それぞれ $1$ から $M$ の番号が振られています.道 $j (1 \leq j \leq M)$ は ダンジョン$a_j$ から ダンジョン$b_j$ を結ぶ一方通行の道であり,移動には $c_j$ 時間かかります.
ダンジョン$i$ を攻略したとき,ダンジョン $i$ を始点とする道が存在する場合,$1$ つ選んでダンジョン間を移動することができ,それ以外にダンジョンを移動する手段は存在しません.また,再度ダンジョン $i$ を訪れた場合でも,再攻略するまで道を選んで移動することはできません.

今,Nafmoくんは ダンジョン $1$ の攻略を始めます.いくつかのダンジョンを経由し,ダンジョン$N$ の攻略とともにゲームを終了したいと思っています.Nafmoくんの満足度は最大でいくつになるかを求めてください.満足度をいくらでも大きくできる場合は inf と出力してください.

ただし,


  • Nafmoくんの満足度:「ダンジョンを攻略するのにかかった時間の総和」 から 「ダンジョン間の移動時間の総和」 を引いたもの
  • 同じダンジョン,同じ道を何度も攻略したり通ったりしても良い
  • ダンジョン攻略から移動の切り替えにかかる時間は無視できるものとする
であるとする.

入力

$N\ M$
$A_1 \ \dots \ A_N$
$a_1 \ b_1 \ c_1$
$\vdots$
$a_M \ b_M \ c_M$



  • $2 \leq N \leq 2500$
  • $1 \leq M \leq min(N\times(N-1),5000)$
  • $1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
  • $1 \leq a_j,b_j \leq N \ (1 \leq j \leq M)$
  • $a_j \neq b_j \ (1 \leq j \leq M)$
  • $a_j \neq a_k$ または $b_j \neq b_k \ (1 \leq j < k \leq M)$
  • $1 \leq c_j \leq 10^9 (1 \leq j \leq M)$ 14:14追記:制約の上限を $N$ から $10^9$ へ修正しました.
  • ダンジョン $1$ から ダンジョン $N$ に到達できる経路が存在する
  • 入力はすべて整数

出力

Nafmoくんの満足度を出力してください

サンプル

サンプル1
入力
3 2
2 2 2
1 2 1
2 3 1
出力
4



ダンジョン$1,2,3$ の順に攻略を行う.()内はそのダンジョンを攻略するのにかかる時間とする.

「ダンジョンを攻略した時間の総和」は $2+2+2=6$ ,「ダンジョン間の移動時間の総和」は $1+1=2$

よって,$6-2=4$ となります.

サンプル2
入力
3 3
2 2 2
1 2 1
2 3 1
2 1 1
出力
inf



頂点$1$,$2$ 間を回り続けることができます.

サンプル3
入力
4 3
594 437 766 437
2 3 63
2 4 10
1 2 61
出力
1397

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。