- Translate each rule into one explicit state update.
- Maintain the invariant after every processed item.
- Return the accumulated state once all relevant input has been handled.
Code notes
- 100 lines of Python from the credited upstream file abc416_e.py.
- The implementation visibly relies on sequence storage, ordered lookup.
- No explicit loop blocks detected.
Complexity
Count the number and nesting of passes over the input, then include the maintained containers in the memory estimate.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4def warshall_floyd(dist):5 """6 Args:7 dist (list[list[int]]): A 2D matrix where dist[i][j] represents the distance 8 from vertex i to vertex j in a graph. If there is no direct edge between 9 i and j, dist[i][j] should be set to a very large value (e.g., infinity).10 11 Returns:12 list[list[int]]: The updated 2D matrix where dist[i][j] contains the shortest 13 distance from vertex i to vertex j. The input matrix is modified in place.14 15 Landau notation: O(n ** 3).16 """17 18 v_count = len(dist[0])19 20 for k in range(v_count):21 for i in range(v_count):22 for j in range(v_count):23 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])24 25 return dist26 27 28def main():29 import sys30 31 input = sys.stdin.readline32 33 n, m = map(int, input().split())34 inf = 10**1835 graph = [[inf for _ in range(n + 1)] for _ in range(n + 1)]36 37 for i in range(n + 1):38 graph[i][i] = 039 40 for _ in range(m):41 ai, bi, ci = map(int, input().split())42 ai -= 143 bi -= 144 45 graph[ai][bi] = min(graph[ai][bi], ci)46 graph[bi][ai] = min(graph[bi][ai], ci)47 48 k, t = map(int, input().split())49 d = list(map(int, input().split()))50 51 52 53 for di in d:54 di -= 155 graph[di][n] = t56 graph[n][di] = 057 58 dist = warshall_floyd(graph)59 60 q = int(input())61 62 for _ in range(q):63 query = list(map(int, input().split()))64 65 if query[0] == 1:66 xi, yi, ti = query[1:]67 xi -= 168 yi -= 169 70 for i in range(n + 1):71 for j in range(n + 1):72 dist1 = dist[i][xi] + ti + dist[yi][j]73 dist2 = dist[i][yi] + ti + dist[xi][j]74 dist[i][j] = min(dist[i][j], dist1, dist2)75 elif query[0] == 2:76 xi = query[1] - 177 78 for i in range(n + 1):79 for j in range(n + 1):80 dist1 = dist[i][xi] + t + dist[n][j]81 dist2 = dist[i][n] + 0 + dist[xi][j]82 dist[i][j] = min(dist[i][j], dist1, dist2)83 else:84 ans = 085 86 for i in range(n):87 for j in range(n):88 if i == j:89 continue90 if dist[i][j] == inf:91 continue92 93 ans += dist[i][j]94 95 print(ans)96 97 98if __name__ == "__main__":99 main()100