結果

問題 No.2569 はじめてのおつかいHard
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-12-02 15:35:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,241 ms / 2,000 ms
コード長 1,671 bytes
コンパイル時間 572 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 211,264 KB
最終ジャッジ日時 2023-12-02 15:36:05
合計ジャッジ時間 9,493 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 496 ms
157,816 KB
testcase_01 AC 436 ms
158,220 KB
testcase_02 AC 454 ms
158,092 KB
testcase_03 AC 439 ms
158,348 KB
testcase_04 AC 481 ms
158,072 KB
testcase_05 AC 1,023 ms
208,740 KB
testcase_06 AC 1,241 ms
194,696 KB
testcase_07 AC 668 ms
209,080 KB
testcase_08 AC 992 ms
211,264 KB
testcase_09 AC 815 ms
189,064 KB
testcase_10 AC 38 ms
53,460 KB
testcase_11 AC 36 ms
53,460 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0