結果
問題 | No.1911 Alternately Coloring |
ユーザー |
|
提出日時 | 2022-01-17 02:19:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,066 ms / 4,000 ms |
コード長 | 2,472 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 84,748 KB |
最終ジャッジ日時 | 2024-11-23 13:35:21 |
合計ジャッジ時間 | 36,339 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
class Dijkstra():class Edge():def __init__(self, _to, _cost):self.to = _toself.cost = _costdef __init__(self, V):self.G = [[] for i in range(V)]self._E = 0self._V = V@propertydef E(self):return self._E@propertydef V(self):return self._Vdef add_edge(self, _from, _to, _cost):self.G[_from].append(self.Edge(_to, _cost))self._E += 1def shortest_path(self, s):import heapqque = []d = [10**15] * self.Vd[s] = 0heapq.heappush(que, (0, s))while len(que) != 0:cost, v = heapq.heappop(que)if d[v] < cost: continuefor i in range(len(self.G[v])):e = self.G[v][i]if d[e.to] > d[v] + e.cost:d[e.to] = d[v] + e.costheapq.heappush(que, (d[e.to], e.to))return dimport sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import log,gcdinput = lambda :sys.stdin.readline()mi = lambda :map(int,input().split())li = lambda :list(mi())def solve(N,M,E,R,B):G = Dijkstra(2*N)edge = [[] for i in range(N)]for u,v in E:u,v = u-1,v-1G.add_edge(2*u,2*v+1,max(R[v]-B[v],0))G.add_edge(2*u+1,2*v,max(B[v]-R[v],0))G.add_edge(2*v,2*u+1,max(R[u]-B[u],0))G.add_edge(2*v+1,2*u,max(B[u]-R[u],0))edge[u].append(v)edge[v].append(u)color = [-1] * Ncolor[0] = 0stack = [0]flag = Truewhile stack:v = stack.pop()for nv in edge[v]:if color[nv]==-1:color[nv] = 1 - color[v]stack.append(nv)else:if color[nv] != 1 - color[v]:flag = Falseif flag:x,y = 0,0for i in range(N):if color[i]:x += R[i]; y += B[i]else:y += R[i]; x += B[i]return max(x,y)res = sum(max(R[i],B[i]) for i in range(N))minus = resfor i in range(N):t0 = G.shortest_path(2*i)[2*i+1]t1 = G.shortest_path(2*i+1)[2*i]minus = min(minus,t0,t1)return res-minusN,M = mi()E = [tuple(mi()) for i in range(M)]R = li()B = li()print(solve(N,M,E,R,B))