Distance Of Colony
原案：牟田
解答：牟田、菅原
英訳：泉
解答状況
0 submit
問題概要
連結な立方体で構成されたコロニーの表面を
通って2点を移動する、最短距離を求めよ
解法
スタート、ゴール、立方体の頂点それぞれの
間の距離を求める
スタート～ゴール
スタート～立方体の頂点
頂点～頂点
頂点～ゴール
ダイクストラ
スタートからゴールまで
直線的に向かう距離
 スタートの面を固定
 展開図のどこにゴールの
面が来うるかを全探査
 展開図と3次元コロニー
の矛盾を検査
矛盾
不採用
無矛盾
無矛盾
最短
各頂点までの距離
前述の方法では実行時間がかかりすぎる
展開図上の頂点が来うる位置に直線を引く
直線をたどってみてどの頂点か調べる
 三次元コロニーのどの頂点に対応するかはどの面を経由するかによって決
定され、展開図上の位置は影響しないことに注意（例：青と赤）
探索範囲について
必ずしも求めたい全ての点間において直線
的に向かう経路が存在するとは限らない
スタートからゴールの上界を先に計算する
それよりも遠い点は探索しない
上界の計算
ワイヤーフレームモデル（辺のみ）でダイクストラ
3 * n * L (全ての立方体でxyz3本の辺を通る)

ピットでの交替の仕方

五島つばきマラソン交通規制（PDF）

美園コース（PDF形式：995KB）

ダウンロード - 東日本大震災復興支援ラン

ダウンロード - 東日本大震災復興支援ラン

第38回南足柄市にこにこ走ろう大会要項

奥山田地区 (ファイル名：okuyamada サイズ：185.44KB)

2日目

P21(90KB) - 袋井市

丸森・耕野 - 阿武隈急行

平成27年度 強歩大会実施要項

第20回三河湾チャリティー100km歩け歩け大会最終案内

水の道・山の道 2015 第 2 回 狩野川遡行＆伊豆山稜線・2 デイズ

とくしまマラソン2015 グッドランナー宣言

第21回三河湾チャリティー100km歩け歩け大会最終案内

チラシ - 東かがわ市

名鉄のハイキング×きんてつハイキング 共同開催コースの

詳細チラシ（PDF） - ようこそ若狭美浜町へ

UFOラインアタック詳細

第15回 開催要項（PDF：195.8KB）

開催日：平成29年1月22日（日）

TOUR DE MINAMISATSUMA 目 的 南さつま市では、市民の健康