nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume10 問題リンク Kuru-Kuru Robot 解法 線分アレンジメントを施したのちダイクストラして解きました。 線分アレンジメントの説明はスパゲッティさんにソースコードと共にあります。ここのソースをおおいに参考にして線分アレンジメントを書きました。オーバーラップしている線分を整理する処理が必要になりますが、それもスパゲッティさんにあります。 線分アレンジメントを施すと、線分の端点と交点が全て列挙され、番号付けされ、更に隣接リストが手に入っている状態になります。 ダイクストラは(現在の頂点、直前の頂点）という拡張頂点にて行います。(b, a)という頂点から(c, b)という頂点へ移るとき、a->b… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20121005%2F1349392180" title="AOJ1033 Kuru-Kuru Robot - nanikakaのAOJ航海日誌" 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 2012-10-05 08:09:40 rich https://nanikaka.hatenadiary.org/entry/20121005/1349392180 1.0 100%