Overview

For each city, we find the “set of cities reachable within patience \(S_i\)”, then use the number of complaints \(C_i\) and the “mutual no-complaint” condition to count the number of friendly pairs.

Analysis

Key Observations

• The condition for representative \(i\) to have no complaint about city \(j\) is \(d(i,j)\le S_i\).
  In other words, what matters for representative \(i\) is not the shortest distance itself, but whether the city is reachable within \(S_i\).
• The number of complaints is $\( C_i = |\{j\ne i \mid d(i,j) > S_i\}| \)\( but this can be rephrased as follows: letting \)cnt_i\( be the number of cities reachable within \)S_i\( (including oneself), \)\( C_i = N - cnt_i \)\( Since \)d(i,i)=0\le S_i$ always holds, there is no off-by-one issue here.

Why the Naive Approach is Difficult

• All-pairs shortest paths (e.g., Floyd-Warshall) takes \(O(N^3)\), which for \(N=400\) amounts to roughly \(64,000,000\) updates and tends to be slow in Python depending on implementation.
• Furthermore, for friendly pair determination, we need checks like “\(d(i,j)\le S_i\)” where the threshold differs for each vertex, so it is natural to construct the “reachable set within \(S_i\)” for each \(i\).

Solution Strategy

• Since edge weights are positive, we run Dijkstra’s algorithm from each city \(i\).
• However, since we don’t need shortest distances exceeding \(S_i\), we cut off the search at \(S_i\) (bounded Dijkstra) to reduce unnecessary work.
• By storing the “set of cities reachable within \(S_i\)” as a bit set (using Python’s int as a bitmask), pair checking becomes fast.

Algorithm

1. Build the graph as an adjacency list (undirected).
2. For each city \(i\), do the following:
   • Set the limit as limit = S[i].
   • Run Dijkstra’s algorithm, but do not explore vertices whose distance exceeds limit.
     • Initialize dist values to INF = limit + 1, so that dist[v] != INF means “reachable within \(S_i\)”.
     • When the distance d extracted from the priority queue exceeds limit, all subsequent distances will only be larger, so we can terminate the search (break).
   • Store the set of reachable vertices as a bitmask mask[i] (set the bit to 1 if reachable).
   • Count the number of reachable vertices as cnt (including oneself), and compute \(C_i = N - cnt\).
3. For all pairs \((i,j)\) (\(i<j\)), count those satisfying:
   • \(C_i = C_j\)
   • and \(j\) is in mask[i] (\(d(i,j)\le S_i\))
   • and \(i\) is in mask[j] (\(d(i,j)\le S_j\))
   • If all conditions hold, add it as a friendly pair.

Bitmask checking can be done in \(O(1)\), for example, checking “\(j\) is in the set” with ((mask[i] >> j) & 1).

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} (M_i \log N)\right) + O(N^2)\)
  Here \(M_i\) is the number of edges actually considered for relaxation during the search bounded by distance \(S_i\), which can be small due to the bounded search. A rough worst-case estimate is \(O(NM\log N)\).
• Space complexity: \(O(N+M)\) (graph) \(+\,O(N)\) (per-run dist, masks/arrays, etc. Each mask is a single int per vertex)

Implementation Notes

• Bounded Dijkstra: Relax only when nd <= limit, and break when d > limit is extracted from the queue for speedup.

• Setting INF = limit + 1 allows checking “reachable within \(S_i\)” with the single condition dist[v] != INF.

• Since \(N\le 400\), it is simple and efficient to use Python’s int as a bit set (just OR with 1<<v).

• The complaint count is computed as \(C_i = N - cnt\) from the reachable count cnt (including oneself), which avoids overthinking the “\(j\ne i\)” in the definition (since oneself is always reachable, it stays consistent).

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    S = [next(it) for _ in range(N)]

    g = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        w = next(it)
        g[u].append((v, w))
        g[v].append((u, w))

    heappush = heapq.heappush
    heappop = heapq.heappop

    masks = [0] * N
    C = [0] * N

    for i in range(N):
        limit = S[i]
        INF = limit + 1
        dist = [INF] * N
        dist[i] = 0
        hq = [(0, i)]
        while hq:
            d, u = heappop(hq)
            if d != dist[u]:
                continue
            if d > limit:
                break
            for v, w in g[u]:
                nd = d + w
                if nd <= limit and nd < dist[v]:
                    dist[v] = nd
                    heappush(hq, (nd, v))

        mask = 0
        cnt = 0
        for v, dv in enumerate(dist):
            if dv != INF:
                mask |= 1 << v
                cnt += 1
        masks[i] = mask
        C[i] = N - cnt

    ans = 0
    for i in range(N):
        mi = masks[i]
        Ci = C[i]
        for j in range(i + 1, N):
            if Ci == C[j] and ((mi >> j) & 1) and ((masks[j] >> i) & 1):
                ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.