hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 問題文と入出力 前提知識 01-BFS 解説 今回の問題は、 damage(sx, sy, tx, ty) := 座標(sx,sy)から座標(tx, ty)へ移るための最小ダメージ として、damage(X[0], Y[0], X[1], Y[1]) + damage(X[1], Y[1], X[2], Y[2]) + ...をしていけばいい。 damage関数の中身は、最短経路問題を解くことになる。 移動先が毒であればコスト1, 移動先が毒でないならコスト0の最短経路問題なので、 これは01-BFSである。 01-BFSはO(状態数)で計算ができるので、これで解こう。 ICPCは実行時間にそ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2019%2F07%2F02%2F064330" title="毒の沼地 [ICPC JAG 模擬国内予選 2019 B] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-07-02 06:43:30 rich https://blog.hamayanhamayan.com/entry/2019/07/02/064330 1.0 100%