結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 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 |
ソースコード
class Graph():def __init__(self,size,directed=False):self.dir=directedself.size=sizeself.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=stself.to=toself.status=statusdef __getitem__(self,val):return self.status[val]inf=pow(2,61)-1from heapq import heappop,heappushdef dijkstra(graph,start,weight):dist=[inf for i in range(graph.size)]used=[False for i in range(graph.size)]dist[start]=0vert=[(0,start)]while len(vert)>0:dis,pos=heappop(vert)if used[pos]:continueused[pos]=Truefor 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 distN,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.statusd1=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)