atcoder.jp 解法 この問題は、0→iに重み$ T_i $の辺と、i→i+1に重み$ S_i $の辺があるグラフと見ることができます。 ここで、0とは高橋君のことを指します。 これで、頂点0からiまでの最短距離は？という問題に変換することができました。 これはダイクスト…

atcoder.jp 水diffになってるけど、適切な位置に出題されていれば茶〜緑ぐらいの難易度だと思った。 考察 dist[i] ← 始点からiまでの最短距離 n.w ← 辺の重み とする。 各頂点を始点としてダイクストラをして、頂点iから元の頂点へ戻る辺を通る時にdist[i] +…

atcoder.jp 解法 問題を見てすぐに下のようなDPが思い浮かんだ。 dp[i][j] ← (i, j)へ行く場合の数 ただ、愚直に遷移しようとすると1つのマスにつき、H+W回ぐらいの遷移が必要になるのでこれでは間に合わない。 手を動かして、DPテーブルがどのような値をと…