Problem F

Problem F
Web 0.5
中嶋・吉野
(出題: 中嶋)
問題
• 放射状のグラフ (部分的に通行不能) 上の
二点を結ぶ最短路の長さを求める
– ただし座標の範囲が
 素直にグラフを作ると十億頂点  TLE, MLE
誤審
• 座標の範囲が
だったのに
のデータが入っていました
• ご迷惑をおかけしました
(特に lambda, echizen)
想定解法
• 必要な頂点のみでグラフを作って Dijkstra
– 以下の r 座標をもつ頂点は通過する可能性あり
• スタート地点の r
• ゴール地点の r
• 損傷した糸の両端の
r ± 1 の範囲
• 巣の中心 (r = 1)
– 頂点数は最大で
(約三万)
他の頂点は不要?
• 二点
を行き来するときに
他の r で曲がると経路が長くなってしまう
• よって，前頁の r のみで十分
審判入力
• 普通の Dijkstra が通ってしまった…?
– ちょっと甘かったかも
– TLE になりそうな例 (今更ですが)
100 99
1 50 10000000 50
9999999 1 10000000 1
9999999 2 10000000 2
...
9999999 98 10000000 98
9999999 99 10000000 99
他にあったミス
• あまり詳しく調べてませんが…
• 巣の中心を通る方が短い場合もあるのを
見落としていた、など

Download Report