結果

問題 No.859 路線A、路線B、路線C
ユーザー 👑 Kazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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]=Weight
self.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:
pass
del self.adjacent[u]
#Walk
#Cycle
#
#
def vertex_exist(self,v):
try:
_=self.adjacent[v]
return True
except:
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
#
#
#Dijkstra
def Dijkstra(G,From,To,with_path=False):
"""Dijksta,FromTo.
G:
From:
To:
with_path:?
()
with_path=True->(,辿)
with_path=False->
"""
from heapq import heappush,heappop
inf=float("inf")
T={v:inf for v in G.adjacent}
T[From]=0
if with_path:
Prev={v:None for v in G.adjacent}
Q=[(0,From)]
Flag=False
while Q:
c,u=heappop(Q)
if u==To:
Flag=True
break
if T[u]<c:
continue
E=G.adjacent[u]
for v in E:
p=T[u]+E[v]
if T[v]>p:
T[v]=p
heappush(Q,(p,v))
if with_path:
Prev[v]=u
if not Flag:
if with_path:
return (inf,None)
else:
return inf
if with_path:
path=[To]
u=To
while (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)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0