結果

問題 No.2604 Initial Motion
ユーザー detteiuudetteiuu
提出日時 2024-12-03 23:35:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,191 bytes
コンパイル時間 455 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 177,596 KB
最終ジャッジ日時 2024-12-03 23:36:27
合計ジャッジ時間 81,433 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
144,192 KB
testcase_01 AC 42 ms
59,048 KB
testcase_02 AC 50 ms
65,860 KB
testcase_03 AC 266 ms
169,932 KB
testcase_04 AC 279 ms
83,500 KB
testcase_05 AC 260 ms
172,804 KB
testcase_06 AC 265 ms
83,128 KB
testcase_07 AC 270 ms
170,232 KB
testcase_08 AC 276 ms
82,980 KB
testcase_09 AC 262 ms
78,252 KB
testcase_10 AC 255 ms
77,664 KB
testcase_11 AC 274 ms
77,548 KB
testcase_12 AC 275 ms
77,892 KB
testcase_13 TLE -
testcase_14 AC 2,547 ms
86,872 KB
testcase_15 AC 1,489 ms
82,964 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 AC 2,686 ms
87,276 KB
testcase_22 TLE -
testcase_23 AC 2,758 ms
87,644 KB
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 2,258 ms
85,324 KB
testcase_28 TLE -
testcase_29 TLE -
testcase_30 AC 2,437 ms
86,240 KB
testcase_31 TLE -
testcase_32 TLE -
testcase_33 AC 767 ms
79,808 KB
testcase_34 AC 2,253 ms
88,300 KB
testcase_35 AC 1,893 ms
89,700 KB
testcase_36 AC 2,189 ms
87,304 KB
testcase_37 AC 1,130 ms
83,712 KB
testcase_38 AC 119 ms
76,196 KB
testcase_39 AC 119 ms
76,160 KB
testcase_40 AC 1,799 ms
83,848 KB
testcase_41 AC 1,763 ms
177,596 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
class Edge:
    def __init__(self, to, cap, cost, rev):
        self.to = to
        self.cap = cap
        self.cost = cost
        self.rev = rev

class MinCostFlow:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(Edge(to, cap, cost, len(self.G[to])))
        self.G[to].append(Edge(fr, 0, -cost, len(self.G[fr])-1))

    def flow(self, s, t, f):
        ans = 0
        H = [0]*self.N
        prv_v = [0]*self.N
        prv_e = [None]*self.N
        dist = [INF]*self.N
        while f:
            dist = [INF]*self.N
            dist[s] = 0
            que = [(0, s)]
            while que:
                d, now = heappop(que)
                if dist[now] < d:
                    continue
                r0 = dist[now] + H[now]
                for e in self.G[now]:
                    if e.cap > 0 and r0 + e.cost - H[e.to] < dist[e.to]:
                        dist[e.to] = r0 + e.cost - H[e.to]
                        prv_v[e.to] = now; prv_e[e.to] = e
                        heappush(que, (dist[e.to], e.to))
            if dist[t] == INF:
                return -1
            for i in range(self.N):
                H[i] += dist[i]
            d = f
            v = t
            while v != s:
                d = min(d, prv_e[v].cap)
                v = prv_v[v]
            f -= d
            ans += d * H[t]
            v = t
            while v != s:
                e = prv_e[v]
                e.cap -= d
                self.G[e.to][e.rev].cap += d
                v = prv_v[v]
        return ans

INF = 10**18

K, N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
edge = [list(map(int, input().split())) for _ in range(M)]

MCF = MinCostFlow(N+2)
for i in range(K):
    MCF.add_edge(N, A[i]-1, 1, 0)
for u, v, d in edge:
    MCF.add_edge(u-1, v-1, INF, d)
    MCF.add_edge(v-1, u-1, INF, d)
for i in range(N):
    MCF.add_edge(i, N+1, B[i], 0)

print(MCF.flow(N, N+1, K))
0