C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008
N人の人が(x[i], y[i])にいる。それぞれ最大t[i]の速度でたこ焼きを投げられ、また最大r[i]までの速度で投げられたたこ焼きをキャッチできる。一人目の人が1秒おきにたこ焼きを投げ、その他の人もたこ焼きを受け取ったらそれを更に別の人に投げることができる。これを繰り返すことで全員にたこ焼きを行き渡らせる時、最小で何秒かかるか？
すべての人のペアについて、min(投げられる最大速度、受け取れる最大速度) の速度でたこ焼きを投げるとして、そのペアについてたこ焼きを投げるのにかかる時間をエッジの長さとしてグラフを構成する。
双方向だがそれぞれのエッジの長さが異なる完全グラフになる。完全グラフなので隣接行列で、最初の人からダイクストラで全員までの距離を計算する。この距離を降順ソートし、順に一秒おきにたこ焼きをその人に向かって投げるという戦略が最適。この時、min(たこ焼きを投げる時間+距離)が最小の時間になる。O(N^2)。
