結果
問題 | No.807 umg tours |
ユーザー | kuro_B |
提出日時 | 2023-03-09 02:45:40 |
言語 | PyPy3 (7.3.13) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,699 bytes |
コンパイル時間 | 1,195 ms |
コンパイル使用メモリ | 81,852 KB |
実行使用メモリ | 391,580 KB |
最終ジャッジ日時 | 2023-10-18 06:05:00 |
合計ジャッジ時間 | 28,259 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 157 ms
88,388 KB |
testcase_01 | AC | 164 ms
88,732 KB |
testcase_02 | AC | 168 ms
88,908 KB |
testcase_03 | AC | 164 ms
88,764 KB |
testcase_04 | AC | 153 ms
88,432 KB |
testcase_05 | AC | 156 ms
88,424 KB |
testcase_06 | AC | 165 ms
88,724 KB |
testcase_07 | AC | 161 ms
88,804 KB |
testcase_08 | AC | 123 ms
82,800 KB |
testcase_09 | AC | 144 ms
88,284 KB |
testcase_10 | AC | 143 ms
88,156 KB |
testcase_11 | AC | 2,763 ms
274,340 KB |
testcase_12 | AC | 2,796 ms
267,556 KB |
testcase_13 | AC | 3,502 ms
346,440 KB |
testcase_14 | AC | 1,628 ms
213,420 KB |
testcase_15 | AC | 1,233 ms
193,420 KB |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
ソースコード
###スニペット始まり### 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')) prev = defaultdict(lambda: None) 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 prev[v] = u heappush(q, (new_cost, v)) return dist, prev N, M = map(int, input().split()) dij=Dijkstra() dij2=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) dij2.add(u-1,v-1, w, True) dij2.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, prev=dij.Dijkstra_search(0) dist2, prev2=dij.Dijkstra_search(0) for i in range(N): print(min(dist[i]*2, dist[i+N]+dist[i]))