結果
問題 | No.1602 With Animals into Institute 2 |
ユーザー |
|
提出日時 | 2021-06-19 16:19:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,027 ms / 4,000 ms |
コード長 | 3,493 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 230,400 KB |
最終ジャッジ日時 | 2024-07-02 02:06:10 |
合計ジャッジ時間 | 37,189 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
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): self.n = n 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 depth[rj]<depth[ri]: self.parent[ri] = rj self.size[rj] += self.size[ri] else: self.parent[rj] = ri self.size[ri] += self.size[rj] return True # グラフの読み込み・重みあり inf = 10**16 n,m,k = map(int, input().split()) ns = [[] for _ in range(n)] ans = [-1]*n h = [] q = [inf]*n parent = list(range(n)) uf = UF(n) d = [-1]*n l = [-1]*n es = [] for e in range(m): u,v,c,x = input().split() u = int(u) v = int(v) c = int(c) x = int(x, 2) u -= 1 v -= 1 ns[u].append((c,x,e,v)) ns[v].append((c,x,e,u)) es.append((u,v,c,x)) ### ダイクストラ dijkstra _val = 1<<20 def to(d,u): return d*_val+u def frm(val): return divmod(val,_val) def dijkstra(start,ns): import heapq vals = [inf] * n h = [to(0, start)] # (距離, ノード番号) vals[start] = 0 ps = [-1]*n ps[start] = (-1,-1,start) # order = [] while h: val, u = frm(heapq.heappop(h)) if val>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 depth = [0]*n 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<hbest[ee]: hp(h, (val2, ee)) for v in range(n-1): if l[v]!=0: ans[v] = d[v] else: ans[v] = q[v] if ans[v]==inf: ans[v] = -1 write("\n".join(map(str, ans[:-1])))