結果
問題 | No.1601 With Animals into Institute |
ユーザー | 👑 Kazun |
提出日時 | 2021-10-11 04:10:32 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,744 bytes |
コンパイル時間 | 550 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 269,616 KB |
最終ジャッジ日時 | 2024-09-15 00:36:38 |
合計ジャッジ時間 | 34,132 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
54,912 KB |
testcase_01 | AC | 47 ms
55,424 KB |
testcase_02 | AC | 46 ms
54,656 KB |
testcase_03 | AC | 178 ms
81,016 KB |
testcase_04 | AC | 155 ms
80,176 KB |
testcase_05 | AC | 163 ms
80,312 KB |
testcase_06 | AC | 2,255 ms
268,544 KB |
testcase_07 | AC | 2,333 ms
269,296 KB |
testcase_08 | AC | 2,183 ms
269,616 KB |
testcase_09 | AC | 2,196 ms
267,060 KB |
testcase_10 | AC | 2,256 ms
267,316 KB |
testcase_11 | AC | 2,211 ms
266,448 KB |
testcase_12 | AC | 2,245 ms
265,776 KB |
testcase_13 | AC | 2,322 ms
268,112 KB |
testcase_14 | AC | 2,253 ms
268,540 KB |
testcase_15 | AC | 2,277 ms
268,104 KB |
testcase_16 | AC | 2,265 ms
267,812 KB |
testcase_17 | AC | 2,284 ms
267,940 KB |
testcase_18 | AC | 170 ms
80,780 KB |
testcase_19 | AC | 164 ms
80,656 KB |
testcase_20 | AC | 157 ms
80,384 KB |
testcase_21 | WA | - |
testcase_22 | AC | 170 ms
80,524 KB |
testcase_23 | AC | 159 ms
80,384 KB |
testcase_24 | AC | 162 ms
80,956 KB |
testcase_25 | AC | 161 ms
80,516 KB |
testcase_26 | AC | 159 ms
80,516 KB |
testcase_27 | AC | 46 ms
55,040 KB |
testcase_28 | AC | 47 ms
54,784 KB |
testcase_29 | AC | 47 ms
55,552 KB |
testcase_30 | WA | - |
testcase_31 | AC | 46 ms
55,680 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 46 ms
55,296 KB |
testcase_35 | AC | 46 ms
55,296 KB |
testcase_36 | AC | 46 ms
54,912 KB |
testcase_37 | WA | - |
testcase_38 | AC | 47 ms
55,552 KB |
ソースコード
class Weigthed_Digraph: """重み[付き]有向グラフを生成する. """ #入力定義 def __init__(self, N): self.N=N self.arc_number=0 self.adjacent_out=[{} for _ in range(N)] #出近傍(vが始点) self.adjacent_in=[{} for _ in range(N)] #入近傍(vが終点) #辺の追加(更新) def add_arc(self, source, target, weight=1): if target not in self.adjacent_out[source]: self.arc_number+=1 self.adjacent_out[source][target]=weight self.adjacent_in[target][source]=weight #辺を除く def remove_arc(self, source, target): if self.arc_exist(source, target): self.arc_number+=1 del self.adjacent_out[source][target] del self.adjacent_in[target][source] #頂点を除く def remove_vertex(self,*vertexes): pass #Walkの追加 def add_walk(self,*walk): pass #Cycleの追加 def add_cycle(self,*cycle): pass #頂点の交換 def __vertex_swap(self,p,q): pass #グラフに辺が存在するか否か def arc_exist(self, source, target): return target in self.adjacent_out[source] #近傍 def neighbohood(self,v): """vの出近傍, 入近傍を出力する. Input: v:頂点 Output: (出近傍, 入近傍) """ return (set(self.adjacent_out[v].keys()),set(self.adjacent_in[v].keys())) #出次数 def out_degree(self,v): return len(self.adjacent_out[v]) #入次数 def in_degree(self,v): return len(self.adjacent_in[v]) #次数 def degree(self,v): return (self.out_degree(v),self.in_degree(v)) #相対次数 def relative_degree(self, v): return self.out_degree(v)-self.in_degree(v) #頂点数 def vertex_count(self): return len(self.vertex) #辺数 def arc_count(self): return self.arc_number #頂点vに到達可能な頂点 def reachable_to(self,v): from collections import deque adj_in=self.adjacent_in T=[0]*self.N; T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in adj_in[x]: if not T[y]: T[y]=1 Q.append(y) return [x for x in range(self.N) if T[x]] #頂点vから到達可能な頂点 def reachable_from(self,v): from collections import deque adj_out=self.adjacent_out T=[0]*self.N; T[v]=1 Q=deque([v]) while Q: x=Q.popleft() for y in adj_out[x]: if T[y]==0: T[y]=1 Q.append(y) return [x for x in range(self.N) if T[x]] #深いコピー def deepcopy(self): from copy import deepcopy D=Weigthed_Digraph(self.N) D.arc_number=self.arc_number D.adjacent_out=deepcopy(self.adjacent_out) D.adjacent_in=deepcopy(self.adjacent_in) return D def Dijkstra_All(D, start, with_path=False): """ Dijksta 法を用いて, 単一始点 start からの距離を求める. D: 辺の重みが全て非負の有向グラフ start: 始点, to: 終点 with_path: 最短路も含めて出力するか? (出力の結果) with_path=True → (距離, 最短経路の辿る際の前の頂点) with_path=False → 距離 """ from heapq import heappush,heappop inf=float("inf") T=[inf]*D.N; T[start]=0 if with_path: prev=[None]*D.N prev[start]=start adj_out=D.adjacent_out Q=[(0, start)] while Q: c,u=heappop(Q) if T[u]<c: continue E=adj_out[u] for v in E: if T[v]>c+E[v]: T[v]=c+E[v] heappush(Q,(T[v],v)) if with_path: prev[v]=u if with_path: return (T,prev) else: return T #================================================== from collections import defaultdict import sys input=sys.stdin.readline write=sys.stdout.write N,M=map(int,input().split()) D=Weigthed_Digraph(2*N) inf=float("inf") Cost=defaultdict(lambda :inf) for _ in range(M): a,b,c,x=map(int,input().split()) a-=1; b-=1 if a>b: a,b=b,a Cost[(a,b,x)]=min(Cost[(a,b,x)],c) for (a,b,x),c in Cost.items(): if x==0: D.add_arc(a,b,c) D.add_arc(b,a,c) D.add_arc(a+N,b+N,c) D.add_arc(b+N,a+N,c) else: D.add_arc(a,b+N,c) D.add_arc(b,a+N,c) D.add_arc(a+N,b+N,c) D.add_arc(b+N,a+N,c) write("\n".join(map(str,Dijkstra_All(D,N-1)[N:2*N-1])))