Overview

This is a problem where you need to find the total number of “friendly pairs” that satisfy certain conditions, using the shortest distances between cities and the patience levels of representatives.

Analysis

In this problem, we first need to find the shortest distances between all pairs of cities. Since the number of cities \(N\) is at most 400, a suitable algorithm for computing all-pairs shortest distances is to run Dijkstra’s algorithm from each vertex (this is faster and simpler to implement than Floyd-Warshall).

Next, for each representative \(i\), we check whether \(d(i, j) > S_i\) for all other cities \(j\), counting the number of such cities to obtain the dissatisfaction count \(C_i\).

Finally, for all distinct representative pairs \((i, j)\) (\(i < j\)), we count those that satisfy the following two conditions as “friendly pairs”:

1. \(d(i, j) \leq S_i\) and \(d(i, j) \leq S_j\): neither is dissatisfied with the other’s city.
2. \(C_i = C_j\): both have the same dissatisfaction count.

In a straightforward approach, running Dijkstra naively from each vertex gives an overall complexity of \(O(N \cdot (N + M) \log N)\), which is sufficiently fast given the constraints. Conversely, using Floyd-Warshall would take \(O(N^3)\) and may result in TLE.

Algorithm

1. Graph Construction
   Build an undirected graph in adjacency list format from the input.

2. All-Pairs Shortest Distance Computation
   Run Dijkstra’s algorithm from each vertex \(i\) to compute \(d(i, j)\) and store the results in a table D.

3. Dissatisfaction Count Computation
   For each representative \(i\), count the number of cities \(j\) such that \(d(i, j) > S_i\), and store the result in array C.

4. Friendly Pair Counting
   For all \(i < j\), count the pairs that satisfy the following conditions:

   • \(D[i][j] \leq S[i]\) and \(D[i][j] \leq S[j]\)
   • \(C[i] == C[j]\)

Complexity

• Time complexity: \(O(N \cdot (N + M) \log N)\)
• Space complexity: \(O(N^2 + M)\)

Implementation Notes

• Vertex numbers are given as 1-indexed in the input, so they need to be converted to 0-indexed for internal processing.

• In Dijkstra’s algorithm, use a priority queue (heapq) to efficiently extract the vertex with the minimum distance.

• float('inf') is used to represent infinity, and comparison operations work correctly with it.

  Source Code

import heapq
import sys

def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    S = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 全点対最短距離を計算
    D = []
    for i in range(N):
        dist = dijkstra(graph, i, N)
        D.append(dist)
    
    # 各代表者の不満の個数 C_i を計算
    C = [0] * N
    for i in range(N):
        count = 0
        for j in range(N):
            if i == j:
                continue
            if D[i][j] > S[i]:
                count += 1
        C[i] = count
    
    # 友好ペアの数を数える
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if D[i][j] <= S[i] and D[i][j] <= S[j] and C[i] == C[j]:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.