結果
問題 | No.807 umg tours |
ユーザー | kuro_B |
提出日時 | 2023-03-09 02:48:16 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,607 bytes |
コンパイル時間 | 687 ms |
コンパイル使用メモリ | 81,800 KB |
実行使用メモリ | 366,280 KB |
最終ジャッジ日時 | 2023-10-18 06:05:47 |
合計ジャッジ時間 | 25,777 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 154 ms
88,216 KB |
testcase_01 | AC | 159 ms
88,536 KB |
testcase_02 | AC | 167 ms
88,696 KB |
testcase_03 | AC | 165 ms
88,528 KB |
testcase_04 | AC | 156 ms
88,208 KB |
testcase_05 | AC | 156 ms
88,216 KB |
testcase_06 | AC | 167 ms
88,520 KB |
testcase_07 | AC | 164 ms
88,596 KB |
testcase_08 | AC | 126 ms
82,580 KB |
testcase_09 | AC | 142 ms
88,072 KB |
testcase_10 | AC | 144 ms
87,952 KB |
testcase_11 | AC | 2,451 ms
266,920 KB |
testcase_12 | AC | 2,501 ms
266,660 KB |
testcase_13 | AC | 3,408 ms
320,212 KB |
testcase_14 | AC | 1,546 ms
198,864 KB |
testcase_15 | AC | 1,129 ms
180,908 KB |
testcase_16 | AC | 3,648 ms
330,892 KB |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | AC | 2,381 ms
267,316 KB |
testcase_21 | AC | 2,222 ms
265,952 KB |
testcase_22 | AC | 993 ms
172,156 KB |
testcase_23 | AC | 823 ms
153,252 KB |
testcase_24 | AC | 1,766 ms
332,324 KB |
testcase_25 | TLE | - |
ソースコード
###スニペット始まり### 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() 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=dij.Dijkstra_search(0) dist2=dij.Dijkstra_search(0) for i in range(N): print(min(dist[i]*2, dist[i+N]+dist[i]))