D - 都市ネットワーク / City Network Editorial by admin
DeepSeek V3Overview
This is a problem where, based on travel times between different cities and each city’s patience, we need to find the number of friendly pairs that satisfy specific conditions.
Analysis
In this problem, we need to count city pairs (i, j) (i < j) that simultaneously satisfy the following three conditions: 1. The shortest travel time \(d(i, j)\) from city i to city j is at most city i’s patience \(S_i\) 2. The shortest travel time \(d(j, i)\) from city j to city i is at most city j’s patience \(S_j\) (since \(d(i, j) = d(j, i)\), this is essentially the same condition) 3. The number of frustrations \(C_i\) and \(C_j\) of city i and city j are equal
A naive approach would directly check the conditions for each city pair, but since \(N \leq 400\), checking all pairs is feasible in \(O(N^2)\). However, we need to precompute the shortest distances between all cities and the number of frustrations for each city.
Algorithm
- All-pairs shortest path computation: Using the Floyd-Warshall algorithm, compute the shortest distance \(d(i, j)\) between all pairs of cities. For unreachable pairs, set the value to a sufficiently large value (INF).
- Counting frustrations: For each city \(i\), examine all other cities \(j\) (excluding \(i\) itself), count the number of cities \(j\) where \(d(i, j) > S_i\), and set this as \(C_i\).
- Counting friendly pairs: For all city pairs \((i, j)\) (\(i < j\)), check whether the three conditions \(d(i, j) \leq S_i\), \(d(i, j) \leq S_j\), and \(C_i = C_j\) are satisfied, and count the number of pairs that meet all conditions.
Complexity
- Time complexity: \(O(N^3)\)
- All-pairs shortest path computation via Floyd-Warshall: \(O(N^3)\)
- Computing the number of frustrations: \(O(N)\) per city, so \(O(N^2)\) in total
- Counting friendly pairs: \(O(N^2)\)
- Space complexity: \(O(N^2)\)
- Storing the distance matrix dist: \(O(N^2)\)
- Storing the frustration count list C: \(O(N)\)
Implementation Notes
During initialization, set the distance for self-loops (i=j) to 0 and all others to INF.
When reading road data, multiple roads may exist between the same pair of cities, so select the minimum weight.
In the Floyd-Warshall algorithm, use the intermediate vertex k as the outer loop, and skip cases where the path does not exist (INF) to avoid unnecessary computation.
When counting the number of frustrations, skip self-loops (i=j).
When counting friendly pairs, skip cases where cities are unreachable (dist[i][j] == INF) as they cannot satisfy the conditions.
Source Code
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()
This editorial was generated by deepseekv3.