水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 064 : E - Cosmic Rays

問題

E - Cosmic Rays

円が N 個あり、できるだけその円の中に入りながらスタート地点からフィニッシュ地点まで行きたい。この時の最短距離を求める問題。

解法

N <= 10^3 と優しいので、円の中心同士の距離をコストとして辺をつくり、グラフを作る。辺の数は N^2 になり、これは 10^6 以内に収まるのでダイクストラ法で最短経路を求める。600 点問題にしては解法が簡単だと感じた(300-400 点問題ぐらい?)

解答

Submission #2865178 - AtCoder Regular Contest 064

600 点問題で1発 AC は初めてかも。

gist.github.com

f:id:babcs2035:20180718213014p:plain