Courses

動的プログラミング

動的グラフプログラミング

Module: 動的グラフプログラミング

Problem

5 /7

DAGへのショートカット

Theory Click to read/hide

動的計画法を使用したソリューションでは、ダイナミクスを計算する順序が重要です (現在の値が依存する値が前に計算されている必要があります)。
したがって、有向非巡回グラフで動的プログラミングを使用する必要がある場合は、最初にグラフのトポロジカルソートを構築する必要があります。次に、構築されたトポロジーソートの順序で頂点をソートしてダイナミクスを計算します (問題に応じて、走査順序はソースからシンクへ、またはその逆になります)。

Problem

有向加重非巡回グラフが与えられます。その中で最短経路を見つける必要があります
頂点 s から頂点 t へ

入力:
入力ファイルの最初の行には、4 つの整数 n、m、s、および t が含まれます。それぞれ、頂点の数、グラフのエッジ、最初と最後の頂点の数です (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
次の m 行には、エッジの説明が 1 行に 1 つずつ含まれています。
エッジ番号 i は、3 つの整数 b_i、e_i および w_i で表されます - それぞれエッジの開始、終了、および長さ ( 1 <= b _i, e_i <= n;|w_i| <= 1000).
グラフにはサイクルとループが含まれていません。

出力:
出力ファイルの最初の行には、単一の整数 (s から t への最短パスの長さ) が含まれている必要があります。
s から t へのパスがない場合は、"Unreachable" と出力します。

例:
<本体>

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking