Description:
点数n(<=100)の重みつきグラフ(G)と、その中のある2点間の最短パス(start-v1-v2-...-goal)が与えられる。
その最短パス中の2点a,bを結ぶ枝eが切れてしまうと、点aまで来ていたパケットは、枝eを使わないaからgoalまでの最短パスを通り、goalに向かうことになる。
このパケットの通った経路の長さと、元の最短パスの長さの差を、枝eのペナルティーと呼ぶ。
最大のペナルティーを求めよ。
Answer:
ある枝が切れたときのペナルティーは、Dijkstra法を用いてO(n^2)で求まる。
与えられたパスの全ての枝に対して実際に枝を1つ切ってグラフを構築しペナルティー計算を行うことで、全体としてO(n^3)で最大ペナルティーを求めることができる。
Source: