結果
問題 | No.807 umg tours |
ユーザー | itsy68 |
提出日時 | 2022-06-10 02:32:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,603 ms / 4,000 ms |
コード長 | 2,557 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 81,468 KB |
実行使用メモリ | 325,444 KB |
最終ジャッジ日時 | 2023-10-21 04:35:31 |
合計ジャッジ時間 | 27,748 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 67 ms
67,976 KB |
testcase_01 | AC | 72 ms
68,220 KB |
testcase_02 | AC | 77 ms
72,372 KB |
testcase_03 | AC | 79 ms
72,664 KB |
testcase_04 | AC | 67 ms
67,976 KB |
testcase_05 | AC | 69 ms
68,224 KB |
testcase_06 | AC | 76 ms
72,368 KB |
testcase_07 | AC | 77 ms
72,588 KB |
testcase_08 | AC | 57 ms
63,280 KB |
testcase_09 | AC | 59 ms
63,280 KB |
testcase_10 | AC | 59 ms
63,280 KB |
testcase_11 | AC | 1,440 ms
233,184 KB |
testcase_12 | AC | 1,382 ms
227,552 KB |
testcase_13 | AC | 2,045 ms
264,596 KB |
testcase_14 | AC | 896 ms
162,468 KB |
testcase_15 | AC | 691 ms
146,224 KB |
testcase_16 | AC | 2,079 ms
267,496 KB |
testcase_17 | AC | 2,539 ms
319,148 KB |
testcase_18 | AC | 2,603 ms
321,832 KB |
testcase_19 | AC | 2,453 ms
325,444 KB |
testcase_20 | AC | 1,187 ms
244,968 KB |
testcase_21 | AC | 1,216 ms
247,652 KB |
testcase_22 | AC | 573 ms
141,672 KB |
testcase_23 | AC | 482 ms
126,556 KB |
testcase_24 | AC | 1,153 ms
276,028 KB |
testcase_25 | AC | 2,531 ms
320,364 KB |
ソースコード
# import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') import sys from itertools import combinations, permutations, product, accumulate, groupby from collections import defaultdict, deque, Counter from functools import reduce from operator import add, mul import heapq import bisect import math import copy sys.setrecursionlimit(10 ** 9) input = lambda: sys.stdin.readline().rstrip() INF = float("inf") MOD = 10 ** 9 + 7 import collections import heapq class Dijkstra(): def __init__(self): self.e = collections.defaultdict(list) def add(self, u, v, d, directed=False): """ #0-indexedでなくてもよいことに注意 #u = from, v = to, d = cost #directed = Trueなら、有向グラフである """ if directed is False: self.e[u].append([v, d]) self.e[v].append([u, d]) else: self.e[u].append([v, d]) def delete(self, u, v): self.e[u] = [_ for _ in self.e[u] if _[0] != v] self.e[v] = [_ for _ in self.e[v] if _[0] != u] def Dijkstra_search(self, s): """ #0-indexedでなくてもよいことに注意 #:param s: 始点 #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev """ d = collections.defaultdict(lambda: float('inf')) prev = collections.defaultdict(lambda: None) d[s] = 0 q = [] heapq.heappush(q, (0, s)) v = collections.defaultdict(bool) while len(q): k, u = heapq.heappop(q) if v[u]: continue v[u] = True for uv, ud in self.e[u]: if v[uv]: continue vd = k + ud if d[uv] > vd: d[uv] = vd prev[uv] = u heapq.heappush(q, (vd, uv)) return d, prev def getDijkstraShortestPath(self, start, goal): _, prev = self.Dijkstra_search(start) shortestPath = [] node = goal while node is not None: shortestPath.append(node) node = prev[node] return shortestPath[::-1] N, M = map(int, input().split()) ABC = [list(map(int, input().split())) for i in range(M)] graph = Dijkstra() for a, b, c in ABC: graph.add(a, b, c) graph.add(a, -b, 0, True) graph.add(b, -a, 0, True) graph.add(-a, -b, c) g, _ = graph.Dijkstra_search(1) print(0) for i in range(2, N + 1): print(g[i] + g[-i])