hotpepsiの練習帳

SRM 622

22:43

Div1 Easy (250) BuildingRoutes

問題

• N個の都市があり、それぞれの都市間経路の距離が与えられる
• ある日、それぞれの都市から、別の全てのそれぞれの都市へ一斉にバスが走る
• バスは最短経路のどれかを通る
• バスが最大T台以上通る可能性がある経路は危険
• 危険な経路の合計の長さを求める

方針

• Warshall-Floydで最短経路を求めておく
• ある経路iからjへの移動について、p->i->j->qという移動に使われる可能性があるかどうかpとqを全列挙する
• p->iへの最短 + i->jの長さ + j->pへの最短 == p->qへの最短ならば使われる可能性がある
• Failed System Test
• (書き直し)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_622/BuildingRoutes.cpp

結果

x-- -2 -50pts 513rd/516 rating 1633 -> 1472 (-161)

添え字を書き間違っていた。

WFの初期値がよくわかっていないが、この問題の場合は同じ地点を0のまま扱うとシンプルになった。

http://togetter.com/li/673231