結果

問題 No.654 Air E869120
コンテスト
ユーザー hotcoffee
提出日時 2025-12-04 14:06:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 972 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 245 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 18,592 KB
最終ジャッジ日時 2025-12-04 14:06:06
合計ジャッジ時間 4,393 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 5
other AC * 10 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def dfs(v, t, f):
    if v == t: return f
    used[v] = True
    for to in G[v]:
        if to not in used and G[v][to] > 0:
            d = dfs(to, t, min(f, G[v][to]))
            if d > 0:
                G[v][to] -= d
                G[to][v] += d
                return d
    return 0

N, M, d = map(int, input().split())
G = {}
G[(1, 0)]      = {}
G[(N, 10**9)] = {}
T = [set() for _ in range(N+1)]
T[1].add(0)
T[N].add(10**9)
for _ in range(M):
    u, v, p, q, c = map(int, input().split())
    if v < N: q += d
    x = (u, p)
    y = (v, q)
    if x not in G: G[x]= {}
    if y not in G: G[y]= {}
    G[x][y] = c
    G[y][x] = 0
    T[u].add(p)
    T[v].add(q)

for i in range(1, N+1):
    t = sorted(T[i])
    for j in range(1, len(t)):
        x = (i, t[j-1])
        y = (i, t[j])
        G[x][y] = float('inf')
        G[y][x] = 0

flow = 0
while True:
    used = {}
    f = dfs((1, 0), (N, 10**9), float('inf'))
    if f == 0: break
    flow += f
print(flow)
0