概要

全都市間の最短コストを求めた後、都市 \(k\) を通る最短経路が存在する条件を、最短距離の等式として判定します。全点対最短経路には Floyd–Warshall 法を用います。

考察

都市 \(i\) から都市 \(j\) への最短経路のうち、都市 \(k\) を内部に含むものが存在する条件を考えます。

そのような最短経路が存在するなら、経路を都市 \(k\) の位置で分けることで、

• 都市 \(i\) から都市 \(k\) まで
• 都市 \(k\) から都市 \(j\) まで

という2つの経路に分解できます。このとき、次の等式が成り立ちます。

\[ d(i,j)=d(i,k)+d(k,j) \]

逆に、この等式が成り立つなら、都市 \(i\) から都市 \(k\) への最短経路と、都市 \(k\) から都市 \(j\) への最短経路を連結できます。そのコストは \(d(i,j)\) と等しいため、連結した経路は都市 \(k\) を通る最短経路になります。

したがって、\(i,j,k\) がすべて異なるとき、求める条件は

\[ d(i,k)+d(k,j)=d(i,j) \]

です。

例えば、

• \(d(i,k)=4\)
• \(d(k,j)=7\)
• \(d(i,j)=11\)

なら、都市 \(k\) を通るコスト \(11\) の経路を作れるため、都市 \(k\) を通る最短経路が存在します。

一方、\(d(i,j)=10\) なら、都市 \(k\) を通る経路のコストは少なくとも \(11\) なので、都市 \(k\) を通る最短経路は存在しません。

素朴な方法の問題点

最短経路を実際に列挙する方法は適しません。最短経路が複数存在する場合、その個数は非常に多くなる可能性があるからです。

また、各 \((i,j,k)\) に対して個別に最短経路を探索すると、最大で \(O(N^3)\) 個の組それぞれについてグラフ探索が必要になり、間に合いません。

そこで、まず Floyd–Warshall 法によって全都市間の最短コストを \(O(N^3)\) で求めます。その後、各 \((i,j,k)\) について上の等式を確認します。この判定も全体で \(O(N^3)\) です。

アルゴリズム

1. \(N \times N\) の配列 dist を用意する。

   • dist[i][i] = 0
   • 道路 \(i \to j\) がある場合は dist[i][j] をその通行料にする。
   • それ以外は到達不能を表す INF にする。

2. Floyd–Warshall 法を実行する。

各都市 \(k\) を中継点として、

$\( \mathrm{dist}[i][j] = \min\left( \mathrm{dist}[i][j], \mathrm{dist}[i][k]+\mathrm{dist}[k][j] \right) \)$

と更新する。

1. 各都市 \(k\) について重要度を数える。

   • \(i=k\) は条件外なので除外する。
   • \(i\) から \(k\) へ到達できない場合も除外する。
   • 各 \(j\) について、

   $\( \mathrm{dist}[i][k]+\mathrm{dist}[k][j] = \mathrm{dist}[i][j] \)$

   なら数える。

2. ただし、問題では \(j=k\) も条件外である。 コードでは \(j=k\) をループ内で一度数えた後、各 \(i\) について count -= 1 として除外している。

3. 各都市の重要度を出力する。

計算量

• 時間計算量: \(O(N^3 + M)\)、全体として \(O(N^3)\)
• 空間計算量: \(O(N^2)\)

実装のポイント

• グラフは有向グラフなので、道路 \(u \to v\) を入力しても dist[v][u] は更新しません。
• 到達不能を表す INF には、あり得る最短コストより十分大きい \(10^{18}\) を使っています。
• i = k は明示的に除外しています。
• j = k については、

$\( \mathrm{dist}[i][k]+\mathrm{dist}[k][k] = \mathrm{dist}[i][k]+0 = \mathrm{dist}[i][k] \)$

が必ず成り立つため、コードでは数えた直後に1を引いています。 - j = i は明示的には除外していませんが、すべての通行料が正なので、

$\( \mathrm{dist}[i][k]+\mathrm{dist}[k][i] > 0 \)$

である一方、\(\mathrm{dist}[i][i]=0\) です。したがって等式は成立せず、自動的に数えられません。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    n = next(it)
    m = next(it)

    INF = 10**18
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    for _ in range(m):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        dist[u][v] = w

    rng = range(n)

    for k in rng:
        dk = dist[k]
        for i in rng:
            di = dist[i]
            dik = di[k]
            if dik == INF:
                continue
            for j in rng:
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    ans = [0] * n

    for k in rng:
        dk = dist[k]
        count = 0
        for i in rng:
            if i == k:
                continue
            di = dist[i]
            dik = di[k]
            if dik == INF:
                continue

            for j in rng:
                if dik + dk[j] == di[j]:
                    count += 1

            # j = k is always counted above, but endpoints must differ from k.
            count -= 1

        ans[k] = count

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.6-sol-high によって生成されました。