A, B, C
1112 -> 1161
C
全探索するのだけど,普通にやると間に合わないので,stepを適切に求めてからする.
D Restoring Road Network
まず,全点対最短経路であるとしてワーシャルフロイドを試し,最短ではなかったら -1 . そのあと,寄り道した場合と直行した場合に長さが同じだったら直行する経路は除く. 残った経路の総和を求める.
A, B, C
1112 -> 1161
全探索するのだけど,普通にやると間に合わないので,stepを適切に求めてからする.
まず,全点対最短経路であるとしてワーシャルフロイドを試し,最短ではなかったら -1 . そのあと,寄り道した場合と直行した場合に長さが同じだったら直行する経路は除く. 残った経路の総和を求める.