Servers (UVa Live Archive Europe - Southwestern - 2002/2003 Porto (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2666

問題

n台のコンピュータで構成されるネットワークがある。ネットワーク上の各コンピュータにはランクrが振られていて、それに応じてお互いのコンピュータの情報を持ち合う。あるコンピュータvが別のコンピュータwの情報を持っているのはdist(v, u)<=dist(v, w)かつr(u)<=r(w)となるコンピュータuが無い時である。このネットワーク上では全体でどの位の情報が保持されているか答えよ。
1<=n<=30000
1<=エッジの数<=5n
1<=r<=10
1<=エッジの重み<=1000
答え<=30n

解法

ランクが高いコンピュータから順にそのコンピュータを出発地点としてダイクストラを行う。その際に枝刈りとして、よりランクの高いコンピュータがより近くにあるようなコンピュータは見ないことにする。答えは30n以下という条件が厳しいのでこれで間に合う。