Internet connection

"""https://cses.fi/345/task/B"""
from __future__ import print_function
import sys

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

def get_path_with_dfs(adj_matrix, adj_list, V):
    """DFS uses a stack/list. BFS uses a queue."""
    root = 1  # Teemu
    target = V  # Taina
    seen = []  # Stuff you've seen.
    to_visit = [root]
    path = []
    while to_visit:
        v = to_visit.pop()  # Pop last inserted element.
        seen.append(v)
        found = False
        for neighbor in adj_list[v]:
            weight = adj_matrix[v][neighbor]
            if (weight < 1) or (neighbor in seen) or (neighbor in path):
                continue
            # eprint(f"weight from {v} to {neighbor} is {weight}")
            found = True
            if neighbor == target:
                path.append(v)
                path.append(target)
                return path
            to_visit.append(neighbor)
            # eprint('to visit', to_visit)
        if found:
            path.append(v)
            # eprint("FOUND: path is ", path)
    return None  # No path found


def max_rate(adj_matrix, adj_list, V):
    total_max_rate = 0
    path = get_path_with_dfs(adj_matrix, adj_list, V)
    while path:
        eprint("path", path)
        path_weights = []
        for i in range(len(path)-1):
            a, b = path[i], path[i+1]
            weight = adj_matrix[a][b]
            path_weights.append(weight)
        eprint('weights', path_weights)

        max_rate = min(path_weights)
        total_max_rate += max_rate
        # Deduct the max_rate from all weights
        for i in range(len(path)-1):
            a, b = path[i], path[i+1]
            adj_matrix[a][b] -= max_rate
            adj_matrix[b][a] += max_rate
        path = get_path_with_dfs(adj_matrix, adj_list, V)
    print(int(total_max_rate))
    return


# Read number oof vertices (computers) and edges (connections).
V, E = [int(x) for x in input().split()]
adj_matrix = [[0 for i in range(V + 1)] for i in range(V + 1)]
adj_list = [[] for _ in range(V+1)]
for i in range(E):
    a, b, weight = [int(x) for x in input().split()]
    adj_matrix[a][b] = weight
    adj_list[a].append(b)
    adj_list[b].append(a)
max_rate(adj_matrix, adj_list, V)

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

path [1, 10]
weights [22]
path [1, 2, 10]
weights [88, 10]
path [1, 2, 9, 10]
weights [78,...

Test 3

Verdict: ACCEPTED

path [1, 2, 6, 10]
weights [26, 42, 50]
path [1, 6, 10]
weights [3, 24]

Test 4

Verdict: ACCEPTED

path [1, 2, 7, 10]
weights [89, 15, 18]
path [1, 2, 3, 8, 9, 10]
weights [74, 42, 71, 38,...

Test 5

Verdict: ACCEPTED

path [1, 10]
weights [81]
path [1, 2, 9, 10]
weights [53, 82, 9]
path [1, 2, 8, 10]
weight...

Test 6

Verdict: ACCEPTED

path [1, 54, 59, 85, 100]
weights [170768914, 255401602, 835234978, 600520102]
path [1, 2,...

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

path [1, 7, 20, 64, 65, 100]
weights [862213124, 121065348, 505661517, 975699204, 53643856...

Test 9

Verdict: ACCEPTED

path [1, 6, 26, 53, 99, 100]
weights [16916041, 205629338, 901388809, 245428508, 472981177...

Test 10

Verdict: ACCEPTED

path [1, 84, 97, 100]
weights [824921463, 107023333, 477356456]
path [1, 84, 85, 86, 97, 1...

Test 11

Verdict: ACCEPTED

path [1, 2]
weights [1]

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

path [1, 2]
weights [1]

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

path [1, 3, 4]
weights [5, 1]
path [1, 3, 2, 4]
weights [4, 2, 3]
path [1, 2, 4]
weights [...

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

path [1, 99, 100]
weights [1000000000, 1000000000]
path [1, 98, 100]
weights [1000000000,...

Test 19

Verdict: ACCEPTED

path [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 2...

Test 20

Verdict: ACCEPTED

path [1, 2]
weights [1]

Test 21

Verdict: ACCEPTED

path [1, 3, 4]
weights [1000000000, 1000000000]
path [1, 2, 4]
weights [1000000000, 100000...

Test 22

Verdict: ACCEPTED

path [1, 3, 4]
weights [1000000000, 1000000000]
path [1, 2, 4]
weights [1000000000, 100000...