結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー |
|
提出日時 | 2024-03-21 16:14:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 160 ms / 5,000 ms |
コード長 | 1,909 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 83,072 KB |
最終ジャッジ日時 | 2024-09-30 10:09:26 |
合計ジャッジ時間 | 5,088 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
import sysimport mathimport bisectfrom heapq import heapify, heappop, heappushfrom collections import deque, defaultdict, Counterfrom functools import lru_cachefrom itertools import accumulate, combinations, permutations, productsys.setrecursionlimit(1000000)MOD = 10 ** 9 + 7MOD99 = 998244353input = lambda: sys.stdin.readline().strip()NI = lambda: int(input())NMI = lambda: map(int, input().split())NLI = lambda: list(NMI())SI = lambda: input()SMI = lambda: input().split()SLI = lambda: list(SMI())EI = lambda m: [NLI() for _ in range(m)]def adjlist(n, edges, directed=False, in_origin=1):if len(edges) == 0:return [[] for _ in range(n)]weighted = True if len(edges[0]) > 2 else Falseif in_origin == 1:if weighted:edges = [[x-1, y-1, w] for x, y, w in edges]else:edges = [[x-1, y-1] for x, y in edges]res = [[] for _ in range(n)]if weighted:for u, v, c in edges:res[u].append([v, c])if not directed:res[v].append([u, c])else:for u, v in edges:res[u].append(v)if not directed:res[v].append(u)return resdef main():N, M, S, G = NMI()ABC = EI(M)Graph = adjlist(N, ABC, in_origin=0)INF = 10**10D = [[INF]*N for _ in range(N)]for i in range(N):D[i][i] = 0for a, b, c in ABC:D[a][b] = cD[b][a] = cfor k in range(N):for i in range(N):for j in range(N):D[i][j] = min(D[i][j], D[i][k] + D[k][j])total = D[S][G]ans = [S]while ans[-1] != G:now = ans[-1]for b, c in sorted(Graph[now]):if c + D[b][G] == total:total -= cans.append(b)breakprint(*ans)if __name__ == "__main__":main()