結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2023-12-30 18:57:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 82 ms / 5,000 ms |
コード長 | 940 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 82,912 KB |
実行使用メモリ | 79,488 KB |
最終ジャッジ日時 | 2024-09-27 16:44:29 |
合計ジャッジ時間 | 4,164 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
from collections import *from itertools import *from functools import *from heapq import *import sys,math,time,randominput = sys.stdin.readlineINF = (1<<60)N,M,S,G = map(int,input().split())e = [[] for _ in range(N)]dist = defaultdict(lambda:defaultdict(lambda:INF))for _ in range(M):u,v,c = map(int,input().split())e[u].append((v,c))e[v].append((u,c))dist[u][v] = cdist[v][u] = cdef dijkstra(s,e):N = len(e)dist = [INF]*Ndist[s]=0h = []heappush(h,(0,s))while h:nw,v = heappop(h)if dist[v]!=nw:continuefor iv,ic in e[v]:nc = ic + nwif nc < dist[iv]:dist[iv] = ncheappush(h,(nc,iv))return distD = dijkstra(G,e)X = [S]while X[-1]!=G:x = X[-1]for i in range(N):if D[i]+dist[i][x] == D[x]:X.append(i)breakprint(*X)