結果

問題 No.2569 はじめてのおつかいHard
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-12-02 15:35:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,054 ms / 2,000 ms
コード長 1,671 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 211,208 KB
最終ジャッジ日時 2024-09-26 18:58:10
合計ジャッジ時間 8,814 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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

class Graph():
def __init__(self,size,directed=False):
self.dir=directed
self.size=size
self.gr=[[] for i in range(size)]
self.edges=[]
def add_edge(self,u,v,status={}):
self.gr[u].append(self.Edge(u,v,status))
if not(self.dir):
self.gr[v].append(self.Edge(v,u,status))
self.edges.append(self.Edge(u,v,status))
def node(self,v):
return self.gr[v]
def __getitem__(self,v):
return self.gr[v]
class Edge():
def __init__(self,st,to,status):
self.st=st
self.to=to
self.status=status
def __getitem__(self,val):
return self.status[val]
inf=pow(2,61)-1
from heapq import heappop,heappush
def dijkstra(graph,start,weight):
dist=[inf for i in range(graph.size)]
used=[False for i in range(graph.size)]
dist[start]=0
vert=[(0,start)]
while len(vert)>0:
dis,pos=heappop(vert)
if used[pos]:
continue
used[pos]=True
for i in graph.node(pos):
if dis+weight(i)<dist[i.to]:
heappush(vert,(dis+weight(i),i.to))
dist[i.to]=dis+weight(i)
return dist
N,M=map(int,input().split())
gr=Graph(N,directed=True)
rev=Graph(N,directed=True)
for i in range(M):
u,v,t=map(int,input().split())
gr.add_edge(u-1,v-1,t)
rev.add_edge(v-1,u-1,t)
w=lambda x:x.status
d1=dijkstra(gr,N-2,w)
d2=dijkstra(gr,N-1,w)
d3=dijkstra(rev,N-2,w)
d4=dijkstra(rev,N-1,w)
for i in range(N-2):
ans=min(d3[i]+d1[N-1]+d2[i],d4[i]+d2[N-2]+d1[i])
if ans>=inf:
print(-1)
else:
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0