結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー | hirayuu_yc |
提出日時 | 2023-12-02 15:34:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,686 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 336,056 KB |
最終ジャッジ日時 | 2023-12-02 15:34:57 |
合計ジャッジ時間 | 15,108 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge9 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 864 ms
267,492 KB |
testcase_01 | AC | 813 ms
267,500 KB |
testcase_02 | AC | 852 ms
267,540 KB |
testcase_03 | AC | 887 ms
267,668 KB |
testcase_04 | AC | 873 ms
267,280 KB |
testcase_05 | AC | 1,680 ms
336,056 KB |
testcase_06 | TLE | - |
testcase_07 | AC | 1,209 ms
332,528 KB |
testcase_08 | AC | 1,625 ms
333,664 KB |
testcase_09 | AC | 1,759 ms
303,448 KB |
testcase_10 | AC | 42 ms
53,588 KB |
testcase_11 | AC | 41 ms
53,588 KB |
ソースコード
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] from math import inf 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,{"w":t}) rev.add_edge(v-1,u-1,{"w":t}) w=lambda x:x["w"] 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)