Overview

Given a graph consisting of \(N\) cities, we compute all-pairs shortest distances, calculate the “number of complaints” for each representative, and count the number of pairs who have no complaints about each other and have equal numbers of complaints.

Analysis

Problem Breakdown

This problem can be solved by performing the following three steps in order:

1. Compute the shortest distance \(d(i, j)\) between all pairs of cities
2. Calculate the number of complaints \(C_i\) for each representative \(i\) (the number of \(j \neq i\) such that \(d(i, j) > S_i\))
3. Count pairs \((i, j)\) (\(i < j\)) that satisfy “\(d(i,j) \leq S_i\) and \(d(i,j) \leq S_j\) and \(C_i = C_j\)”

Which Algorithm to Use for Shortest Distances

We need shortest distances between all pairs of cities. The options are:

• Running Dijkstra’s algorithm from each vertex: \(O(N(M \log N))\)
• Floyd–Warshall algorithm: \(O(N^3)\)

Since \(N \leq 400\), we have \(N^3 = 64{,}000{,}000\), which is manageable with Floyd–Warshall. Its implementation is also simple, so we adopt this approach.

Is a Naive Brute Force Sufficient?

Computing \(C_i\) takes \(O(N)\) per representative, \(O(N^2)\) in total. Checking friendly pairs can also be done over all pairs in \(O(N^2)\). The bottleneck is Floyd–Warshall at \(O(N^3)\), but since \(N \leq 400\), there is no issue.

Algorithm

Step 1: All-Pairs Shortest Distances (Floyd–Warshall)

Initialize the distance matrix \(\text{dist}[i][j]\): - \(\text{dist}[i][i] = 0\) - If there is an edge \((u, v, w)\), set \(\text{dist}[u][v] = \text{dist}[v][u] = w\) - All other entries are \(\infty\)

Then, iterate the intermediate vertex \(k\) from \(0\) to \(N-1\) and perform the following update:

\[\text{dist}[i][j] = \min(\text{dist}[i][j], \; \text{dist}[i][k] + \text{dist}[k][j])\]

Step 2: Computing the Number of Complaints \(C_i\)

For each representative \(i\), count the number of \(j\) such that \(j \neq i\) and \(d(i, j) > S_i\). Unreachable cities (\(d(i,j) = \infty\)) are also counted as complaints since \(S_i\) is finite.

Step 3: Counting Friendly Pairs

For all pairs \((i, j)\) (\(i < j\)), check all three of the following conditions: 1. \(d(i, j) \leq S_i\) 2. \(d(i, j) \leq S_j\) 3. \(C_i = C_j\)

The number of pairs satisfying all conditions is the answer.

Concrete Example

For example, with \(N = 3\), distance between cities 1–2 being \(5\), distance between cities 2–3 being \(3\), and \(S = [5, 10, 2]\): - \(d(1,2)=5, d(1,3)=8, d(2,3)=3\) - \(C_1 = |\{3\}| = 1\) (\(d(1,3)=8 > 5\)) - \(C_2 = 0\) (both are at most \(10\)) - \(C_3 = |\{1, 2\}| = 2\) (\(d(3,1)=8>2, d(3,2)=3>2\)) - Pair \((1,2)\): \(d=5 \leq 5\) and \(d=5 \leq 10\), but \(C_1 \neq C_2\) → not valid - The number of friendly pairs is \(0\)

Complexity

• Time complexity: \(O(N^3)\) (Floyd–Warshall is the bottleneck)
• Space complexity: \(O(N^2)\) (storing the distance matrix)

Implementation Notes

• Handling \(\infty\): Using Python’s float('inf') is convenient since addition and comparison work naturally. When using a large integer value (e.g., \(10^{18}\)), you need to be careful about overflow, but float('inf') eliminates that concern.

• Speeding up Floyd–Warshall: Since triple nested loops are slow in Python, pruning by early skipping (continue) when dist[i][k] == INF in the inner loop is effective. Also, extracting dist[k] and dist[i] into local variables reduces attribute access overhead and improves the constant factor.

• Fast input reading: Using sys.stdin.buffer.read() for bulk reading avoids I/O bottlenecks when dealing with large inputs.

  Source Code

import sys
import heapq

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(input_data[idx]); idx += 1
    
    INF = float('inf')
    
    # Floyd-Warshall for N <= 300
    dist = [[INF] * N for _ in range(N)]
    for i in range(N):
        dist[i][i] = 0
    
    for k in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w
    
    # Floyd-Warshall
    for k in range(N):
        dk = dist[k]
        for i in range(N):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(N):
                new_dist = dik + dk[j]
                if new_dist < di[j]:
                    di[j] = new_dist
    
    # Compute C_i for each representative
    C = [0] * N
    for i in range(N):
        si = S[i]
        ci = 0
        di = dist[i]
        for j in range(N):
            if j != i and di[j] > si:
                ci += 1
        C[i] = ci
    
    # Count friendly pairs
    count = 0
    for i in range(N):
        si = S[i]
        ci = C[i]
        di = dist[i]
        for j in range(i + 1, N):
            dij = di[j]
            if dij <= si and dij <= S[j] and ci == C[j]:
                count += 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.