import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) class UF: # unionfind def __init__(self, n, depth): self.n = n self.depth = depth self.parent = list(range(n)) self.size = [1] * n def check(self): return [self.root(i) for i in range(self.n)] def root(self, i): inter = set() while self.parent[i]!=i: inter.add(i) i = self.parent[i] r = i for i in inter: self.parent[i] = r return r def connect(self, i, j): # 繋いだかどうかを返す ri = self.root(i) rj = self.root(j) if ri==rj: return False if self.depth[rj]>i&1 if not vv: add(u,n+v,c) add(v,n+u,c) else: add(u,v,c) add(n+u,n+v,c) for u in range(n-1): if u==s: continue add(u,n+u,0) g.remove_node(n+s) g.remove_node(2*n-1) res = nx.max_weight_matching(g, maxcardinality=True) if len(res)vals[u]: continue # order.append(u) for d,x,e,v in ns[u]: if vals[v]>val+d: vals[v] = val+d heapq.heappush(h, to(vals[v], v)) ps[v] = (d,x,u) return vals, ps vals, ps = dijkstra(n-1, ns) ns2 = [[] for _ in range(n)] for i,(dd,x,v) in enumerate(ps[:-1]): ns2[i].append((dd,x,v)) ns2[v].append((dd,x,i)) qq = [n-1] d[n-1] = 0 l[n-1] = 0 while qq: u = qq.pop() for dd,x,v in ns2[u]: if d[v]>=0: continue d[v] = d[u] + dd l[v] = l[u] ^ x depth[v] = depth[u] + 1 qq.append(v) from heapq import heappop as hpp, heappush as hp, heapify hbest = [inf]*m for e,(u,v,c,x) in enumerate(es): if l[u]^x!=l[v]: h.append((d[u]+d[v]+c, e)) heapify(h) while h: val, e = hpp(h) if val>=inf: break if val>hbest[e]: continue hbest[e] = val u,v,c,x = es[e] w1 = uf.root(u) w2 = uf.root(v) b = [] while w1!=w2: if depth[w1]<=depth[w2]: b.append(w2) w2 = uf.root(ps[w2][2]) else: b.append(w1) w1 = uf.root(ps[w1][2]) # print(w1,w2) for ww in b: uf.connect(w1,ww) # q[ww] = min(q[ww], val - d[w1]) q[ww] = val - d[ww] for cc,xx,ee,vv in ns[ww]: val2 = q[ww] + d[vv] + cc if val2