結果
問題 | No.807 umg tours |
ユーザー | kuro_B |
提出日時 | 2023-03-09 02:50:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,532 ms / 4,000 ms |
コード長 | 3,498 bytes |
コンパイル時間 | 1,654 ms |
コンパイル使用メモリ | 81,588 KB |
実行使用メモリ | 284,916 KB |
最終ジャッジ日時 | 2023-10-18 06:06:17 |
合計ジャッジ時間 | 28,362 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 147 ms
88,212 KB |
testcase_01 | AC | 146 ms
88,212 KB |
testcase_02 | AC | 151 ms
88,232 KB |
testcase_03 | AC | 152 ms
88,208 KB |
testcase_04 | AC | 150 ms
88,208 KB |
testcase_05 | AC | 151 ms
88,232 KB |
testcase_06 | AC | 153 ms
88,208 KB |
testcase_07 | AC | 149 ms
88,216 KB |
testcase_08 | AC | 123 ms
82,648 KB |
testcase_09 | AC | 125 ms
82,652 KB |
testcase_10 | AC | 127 ms
82,656 KB |
testcase_11 | AC | 1,465 ms
222,332 KB |
testcase_12 | AC | 1,435 ms
213,968 KB |
testcase_13 | AC | 1,802 ms
252,896 KB |
testcase_14 | AC | 897 ms
161,972 KB |
testcase_15 | AC | 717 ms
146,416 KB |
testcase_16 | AC | 2,147 ms
262,740 KB |
testcase_17 | AC | 2,532 ms
284,916 KB |
testcase_18 | AC | 2,419 ms
282,884 KB |
testcase_19 | AC | 2,356 ms
280,580 KB |
testcase_20 | AC | 1,190 ms
223,808 KB |
testcase_21 | AC | 1,190 ms
226,736 KB |
testcase_22 | AC | 605 ms
143,176 KB |
testcase_23 | AC | 523 ms
130,008 KB |
testcase_24 | AC | 1,097 ms
263,660 KB |
testcase_25 | AC | 2,462 ms
283,580 KB |
ソースコード
###スニペット始まり### import sys, re from math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2 from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import permutations, accumulate, product, combinations, combinations_with_replacement from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from string import ascii_uppercase, ascii_lowercase from decimal import Decimal, ROUND_HALF_UP #四捨五入用 def input(): return sys.stdin.readline().rstrip('\n') #easy-testでは再帰数を下げる。 if __file__=='prog.py': sys.setrecursionlimit(10**5) else: sys.setrecursionlimit(10**6) def lcm(a, b): return a * b // gcd(a, b) #3つ以上の最大公約数/最小公倍数 def gcd_v2(l: list): return reduce(gcd, l) def lcm_v2(l: list): return reduce(lcm, l) #nPk def nPk(n, k): return factorial(n) // factorial(n - k) #逆元 def modinv(a, mod=10**9+7): return pow(a, mod-2, mod) INF = float('inf') MOD = 10 ** 9 + 7 ###スニペット終わり### class Dijkstra(): def __init__(self): self.e = defaultdict(list) def add(self, u, v, cost, directed=False): """ #0-indexedでなくてもよいことに注意 #u = from, v = to, d = cost #directed = Trueなら、有向グラフである """ if directed is False: self.e[u].append([v, cost]) self.e[v].append([u, cost]) else: self.e[u].append([v, cost]) #無向用っぽい 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] #多分この実装は、O(V + ElogE)の計算量。Vはグラフ作成、最初のヒープからの取り出しでElogE。その後の探索でElogE def Dijkstra_search(self, s): """ #0-indexedでなくてもよいことに注意 #:param s: 始点 #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev """ dist = defaultdict(lambda: float('inf')) dist[s] = 0 q = [] heappush(q, (0, s)) #点が確定済みかどうか。 fixed = defaultdict(bool) while len(q): total_cost, u = heappop(q) if fixed[u]: #すでに確定した頂点を取り出すこともあるので、ここで除いている。誤ってTrueにしないため。 continue fixed[u] = True for v, cost in self.e[u]: if fixed[v]: continue #total_costは更新しないようにする。複数辺があるため。 new_cost = total_cost + cost if dist[v] > new_cost: dist[v] = new_cost heappush(q, (new_cost, v)) return dist N, M = map(int, input().split()) dij=Dijkstra() for _ in range(M): u, v, w = map(int, input().split()) dij.add(u-1,v-1, w, True) dij.add(v-1, u-1, w, True) #裏の拡張頂点へ辺を通す。Nを足す。コストは0 dij.add(u-1,N+v-1, 0, True) dij.add(v-1, N+u-1, 0, True) #裏頂点から裏頂点に辺を通す。 dij.add(N+u-1, N+v-1, w, True) dij.add(N+v-1, N+u-1, w, True) dist=dij.Dijkstra_search(0) for i in range(N): print(min(dist[i]*2, dist[i+N]+dist[i]))