SRM622Div1Easy
問題
N個()の頂点を持ち、dist[i][j](
)のコストの一方向の辺を持つグラフが与えられる。それぞれの頂点からそれぞれの頂点への最短路を考えた時、T(
)より多い回数を通る辺のコストの総和を求めよ。
解法
d[i][j]は最短路のコストを表す。ある辺が最短路に含まれるかどうかは、以下の式で判断できる。
上の条件を満たすのなら、xからyへの辺はaからbへの最短路に含まれる。全ての頂点に対して調べることで、それぞれの辺が最短路となる回数が求める。この回数がTより大きいかを調べることで答えが求まる。
計算量
N: 頂点数
