概要

異なる都市間の移動時間と各都市の忍耐力をもとに、特定の条件を満たす友好ペアの数を求める問題です。

考察

この問題では、以下の3つの条件を同時に満たす都市ペア(i, j)（i < j）を数える必要があります： 1. 都市iから都市jへの最短移動時間 \(d(i, j)\) が、都市iの忍耐力 \(S_i\) 以下である 2. 都市jから都市iへの最短移動時間 \(d(j, i)\) が、都市jの忍耐力 \(S_j\) 以下である（\(d(i, j) = d(j, i)\) なので実質同じ条件） 3. 都市iと都市jの不満の個数 \(C_i\) と \(C_j\) が等しい

素朴なアプローチでは、各都市ペアについて直接条件をチェックすることになりますが、\(N \leq 400\) なので全ペアのチェックは \(O(N^2)\) で十分可能です。ただし、事前にすべての都市間の最短距離と各都市の不満の個数を計算しておく必要があります。

アルゴリズム

1. 全点対最短経路の計算: Floyd-Warshallアルゴリズムを用いて、すべての都市間の最短距離 \(d(i, j)\) を計算します。到達不能な場合は十分大きな値（INF）を設定します。
2. 不満の個数の計算: 各都市 \(i\) について、\(i\) 以外のすべての都市 \(j\) を調べ、\(d(i, j) > S_i\) となる \(j\) の個数を数えて \(C_i\) とします。
3. 友好ペアのカウント: すべての都市ペア \((i, j)\)（\(i < j\)）について、\(d(i, j) \leq S_i\) かつ \(d(i, j) \leq S_j\) かつ \(C_i = C_j\) の3条件を満たすかをチェックし、条件を満たすペアの数を数えます。

計算量

• 時間計算量: \(O(N^3)\)
  • Floyd-Warshallアルゴリズムによる全点対最短経路計算: \(O(N^3)\)
  • 不満の個数の計算: 各都市について \(O(N)\) なので合計 \(O(N^2)\)
  • 友好ペアのカウント: \(O(N^2)\)
• 空間計算量: \(O(N^2)\)
  • 距離行列 dist の保持: \(O(N^2)\)
  • 不満の個数リスト C の保持: \(O(N)\)

実装のポイント

• 初期化時に、自己ループ（i=j）の距離を0に、それ以外をINFに設定します。

• 道路データの入力時に、同じ都市間で複数の道路が存在する可能性があるため、最小の重みを選択します。

• Floyd-Warshallアルゴリズムでは、中間点kを外側ループとし、経路が存在しない場合（INF）はスキップすることで無駄な計算を避けます。

• 不満の個数を数える際、自分自身（i=j）はスキップする必要があります。

• 友好ペアを数える際、都市間が到達不能（dist[i][j] == INF）な場合は条件を満たさないのでスキップします。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    S = [0] * (n+1)
    for i in range(1, n+1):
        S[i] = int(next(it))
        
    INF = 10**18
    dist = [[INF] * (n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        dist[i][i] = 0
        
    for _ in range(m):
        u = int(next(it)); v = int(next(it)); w = int(next(it))
        if dist[u][v] > w:
            dist[u][v] = w
            dist[v][u] = w
            
    for k in range(1, n+1):
        for i in range(1, n+1):
            if dist[i][k] == INF:
                continue
            for j in range(1, n+1):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    
    C = [0] * (n+1)
    for i in range(1, n+1):
        count = 0
        for j in range(1, n+1):
            if i == j:
                continue
            if dist[i][j] > S[i]:
                count += 1
        C[i] = count
        
    ans = 0
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if dist[i][j] == INF:
                continue
            if dist[i][j] <= S[i] and dist[i][j] <= S[j] and C[i] == C[j]:
                ans += 1
                
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。