CF 25C - Roads in Berland

Rating: 1900
Tags: graphs, shortest paths
Solve time: 58s
Verified: yes

Solution

Problem Understanding

We are given a map of n cities in Berland, where the shortest distances between all pairs are already known. Conceptually, this means the country is fully connected via some unknown set of roads, and the distance matrix is already the all-pairs shortest path result. The government plans to add k new roads, and after each addition, they want the sum of the shortest distances between every pair of cities.

Input provides the shortest distance matrix d and the list of planned roads with their endpoints and lengths. Our task is to simulate adding these roads one by one and compute the new sum of shortest paths efficiently. The output is a list of sums, one per road addition.

The constraints are tight but manageable. With n up to 300, a naive recomputation of all-pairs shortest paths after each road using Floyd-Warshall would be O(n³ * k), which in the worst case is 300³ * 300 = 8.1 × 10^9 operations, far too slow. We need a more clever update mechanism.

Non-obvious edge cases include situations where adding a road does not directly shorten the distance between its two endpoints but indirectly improves paths between other cities. For instance, if the matrix initially has d[1][2] = 10 and d[1][3] = 5, d[3][2] = 4, then adding a direct road from 1 to 2 of length 7 does not directly change d[1][2] since 10 > 7, but we must also check whether any other path combinations reduce other distances. Careless implementations that update only the direct endpoints would produce incorrect sums.

Approaches

A brute-force solution would be to add each new road and run Floyd-Warshall to recompute all shortest distances. Floyd-Warshall’s complexity is O(n³), so repeating it for k roads gives O(k * n³). This is correct but infeasible for n, k ~ 300. The sum of pairs could be computed trivially once the matrix is recomputed.

The key observation is that each new road (a, b, c) only affects distances if it creates a shorter path via a or b. Specifically, for any pair (i, j), the new shortest distance is:

d[i][j] = min(d[i][j], d[i][a] + c + d[b][j], d[i][b] + c + d[a][j])

This formula checks whether going through the new road reduces the path between any two cities. We iterate through all pairs (i, j) using this update. Since the matrix is symmetric and we only need unordered pairs, we can iterate i from 1 to n and j from i+1 to n, reducing unnecessary computation.

This reduces the per-road update to O(n²), giving total complexity O(k * n²), which is acceptable for n, k ≤ 300 (around 27 million operations in the worst case).

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (Floyd-Warshall per road)	O(k * n³)	O(n²)	Too slow
Optimal (direct path update using new road)	O(k * n²)	O(n²)	Accepted

Algorithm Walkthrough

Read the initial shortest distance matrix d and store it. Since the input already guarantees all-pairs shortest distances, no preprocessing is required.
Initialize a variable sum_pairs to the sum of all unordered pairs (i, j) in d. We only sum i < j to avoid double-counting.
For each planned road (a, b, c), iterate through all pairs (i, j) and check if routing via this road shortens the path:

Compute d[i][a] + c + d[b][j] and d[i][b] + c + d[a][j].
If either is smaller than the current d[i][j], update d[i][j] to the minimum.
For i < j, adjust sum_pairs incrementally by subtracting the old d[i][j] and adding the new value.

After processing the current road, append sum_pairs to the results list. Continue to the next road.
Output the results list at the end.

Why it works: The update formula ensures that all potential new shortest paths involving the newly added road are considered. Since d always contains the shortest distances at the start of each iteration, iteratively applying this update preserves correctness for all pairs. Summing only for i < j avoids double-counting.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]

k = int(input())
roads = [tuple(map(int, input().split())) for _ in range(k)]

# Adjust indices to 0-based
d = [[d[i][j] for j in range(n)] for i in range(n)]
sum_pairs = sum(d[i][j] for i in range(n) for j in range(i+1, n))

res = []

for a, b, c in roads:
    a -= 1
    b -= 1
    for i in range(n):
        for j in range(n):
            # Check if a path through the new road improves distance
            new_dist = min(d[i][j], d[i][a] + c + d[b][j], d[i][b] + c + d[a][j])
            if new_dist < d[i][j]:
                if i < j:
                    sum_pairs -= d[i][j]
                    sum_pairs += new_dist
                d[i][j] = new_dist
    res.append(sum_pairs)

print(" ".join(map(str, res)))

Each section of the code directly implements the algorithm steps. We carefully adjust the indices to zero-based. The incremental update of sum_pairs avoids recomputing the full sum from scratch after each road. Iterating over all (i, j) ensures no potential new shorter paths are missed.

Worked Examples

Sample 1

Input:

i	j	Old d[i][j]	d[i][a]+c+d[b][j]	d[i][b]+c+d[a][j]	New d[i][j]	sum_pairs
0	1	5	0+3+0=3	0+3+0=3	3	3

Output: 3

This shows the algorithm correctly updates the only pair when a new road shortens it.

Custom Example

Input:

Trace:

i	j	Old	via new road	New	sum_pairs
0	1	5	0+1+3=4	4	6
0	2	2	0+1+0=1	1	5
1	2	3	1+1+2=4	3	5

Output: 5

The update correctly accounts for all paths affected by the new road.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * n²)	Each road may update all n² entries in the distance matrix.
Space	O(n²)	We store the distance matrix explicitly.

With n ≤ 300 and k ≤ 300, the total number of operations is roughly 27 million, well within the 2-second limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n = int(input())
    d = [list(map(int, input().split())) for _ in range(n)]
    k = int(input())
    roads = [tuple(map(int, input().split())) for _ in range(k)]
    d = [[d[i][j] for j in range(n)] for i in range(n)]
    sum_pairs = sum(d[i][j] for i in range(n) for j in range(i+1, n))
    res = []
    for a, b, c in roads:
        a -= 1
        b -= 1
        for i in range(n):
            for j in range(n):
                new_dist = min(d[i][j], d[i][a]+c+d[b][j], d[i][b]+c+d[a][j])
                if new_dist < d[i][j]:
                    if i < j:
                        sum_pairs -= d[i][j]
                        sum_pairs += new_dist
                    d[i][j] = new_dist
        res.append(sum_pairs)
    return " ".join(map(str, res))

# Provided sample
assert run("2\n0 5\n5 0\n1\n1 2