3463

問題

有向グラフが与えられる。開始点と終了点が与えられるので、最短距離またはその+1までのパスは何通りあるか答えよ、という問題。

解答例

まずダイクストラで、開始点からの最短距離を全部の点について求める。再度ダイクストラで、最短距離またはその+1について、何通りの到達方法があるかを計算していく。両方のステップをマージして一度で終えることもできなくはないが、コードが煩雑になるので避けた方が良い。

なお、グラフは辺をリスト形式で与えられ、同じ長さの辺が複数あったり、長さが+1の辺が複数あったりするので、適宜入力を管理する必要があり、それが問題の本質よりも難易度が高い...。