結果
問題 | No.859 路線A、路線B、路線C |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-29 18:38:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 1,000 ms |
コード長 | 3,992 bytes |
コンパイル時間 | 271 ms |
コンパイル使用メモリ | 82,264 KB |
実行使用メモリ | 53,888 KB |
最終ジャッジ日時 | 2024-06-27 05:20:10 |
合計ジャッジ時間 | 1,693 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
class Weigthed_Graph:#入力定義def __init__(self,vertex=[]):self.adjacent={v:{} for v in vertex}#頂点の追加def add_vertex(self,*adder):for u in adder:if u not in self.adjacent:self.adjacent[u]={}#辺の追加def add_edge(self,u,v,Weight):if u not in self.adjacent:self.add_vertex(u)if v not in self.adjacent:self.add_vertex(v)self.adjacent[u][v]=Weightself.adjacent[v][u]=Weight#辺を除くdef remove_edge(self,u,v):for w in [u,v]:if w not in self.adjacent:self.add_vertex(w)try:del self.adjacent[u][v]del self.adjacent[v][u]except:pass#頂点を除くdef remove_vertex(self,*v):for u in v:for w in self.vertex:try:del self.adjacent[w][u]except:passdel self.adjacent[u]#Walkの追加#Cycleの追加#頂点の交換#グラフに頂点が存在するか否かdef vertex_exist(self,v):try:_=self.adjacent[v]return Trueexcept:return False#グラフに辺が存在するか否かdef edge_exist(self,u,v):return v in self.adjacent[u]#出近傍def in_neighbohood(self,v):try:return list(self.adjacent[v].keys())except:return None#出次数def in_degree(self,v):try:return len(self.adjacent[v])except:pass#頂点数def vertex_count(self):return len(self.adjacent)#辺数#頂点vを含む連結成分#距離#最短路#Dijkstradef Dijkstra(G,From,To,with_path=False):"""Dijksta法を用いて,FromからToまでの距離を求める.G:辺の重みが全て非負の無向グラフFrom:始点To:終点with_path:最短路も含めて出力するか?(出力の結果)with_path=True->(距離,最短経路の辿る際の前の頂点)with_path=False->距離"""from heapq import heappush,heappopinf=float("inf")T={v:inf for v in G.adjacent}T[From]=0if with_path:Prev={v:None for v in G.adjacent}Q=[(0,From)]Flag=Falsewhile Q:c,u=heappop(Q)if u==To:Flag=Truebreakif T[u]<c:continueE=G.adjacent[u]for v in E:p=T[u]+E[v]if T[v]>p:T[v]=pheappush(Q,(p,v))if with_path:Prev[v]=uif not Flag:if with_path:return (inf,None)else:return infif with_path:path=[To]u=Towhile (Prev[u]!=None):u=Prev[u]path.append(u)return (T[To],path[::-1])else:return T[To]#================================================x,y,z=map(int,input().split())A,B,C="ABC"D=Weigthed_Graph()D.add_edge((A,1),(A,x),x-1)D.add_edge((B,1),(B,y),y-1)D.add_edge((C,1),(C,z),z-1)D.add_edge((A,1),(B,1),1)D.add_edge((B,1),(C,1),1)D.add_edge((C,1),(A,1),1)D.add_edge((A,x),(B,y),1)D.add_edge((B,y),(C,z),1)D.add_edge((C,z),(A,x),1)S,s=input().split();s=int(s)if S==A:D.add_edge((A,1),(A,s),s-1)D.add_edge((A,s),(A,x),x-s)elif S==B:D.add_edge((B,1),(B,s),s-1)D.add_edge((B,s),(B,y),y-s)else:D.add_edge((C,1),(C,s),s-1)D.add_edge((C,s),(C,z),z-s)T,t=input().split();t=int(t)if T==A:D.add_edge((A,1),(A,t),t-1)D.add_edge((A,t),(A,x),x-t)elif T==B:D.add_edge((B,1),(B,t),t-1)D.add_edge((B,t),(B,y),y-t)else:D.add_edge((C,1),(C,t),t-1)D.add_edge((C,t),(C,z),z-t)if S==T:D.add_edge((S,s),(T,t),abs(s-t))print(Dijkstra(D,(S,s),(T,t)))