結果
問題 | No.1601 With Animals into Institute |
ユーザー | SI1000-github |
提出日時 | 2022-03-24 22:41:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,630 bytes |
コンパイル時間 | 331 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 202,752 KB |
最終ジャッジ日時 | 2024-04-21 07:39:40 |
合計ジャッジ時間 | 45,461 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
53,376 KB |
testcase_01 | AC | 50 ms
53,376 KB |
testcase_02 | AC | 50 ms
53,632 KB |
testcase_03 | AC | 165 ms
80,072 KB |
testcase_04 | AC | 179 ms
80,128 KB |
testcase_05 | AC | 179 ms
80,000 KB |
testcase_06 | AC | 2,750 ms
200,192 KB |
testcase_07 | TLE | - |
testcase_08 | AC | 2,943 ms
200,960 KB |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | AC | 179 ms
80,296 KB |
testcase_19 | AC | 179 ms
80,760 KB |
testcase_20 | AC | 184 ms
80,476 KB |
testcase_21 | AC | 178 ms
80,000 KB |
testcase_22 | AC | 174 ms
80,256 KB |
testcase_23 | AC | 181 ms
80,748 KB |
testcase_24 | AC | 180 ms
80,488 KB |
testcase_25 | AC | 176 ms
80,480 KB |
testcase_26 | AC | 180 ms
80,256 KB |
testcase_27 | AC | 50 ms
53,376 KB |
testcase_28 | AC | 50 ms
53,248 KB |
testcase_29 | AC | 49 ms
53,760 KB |
testcase_30 | AC | 49 ms
53,632 KB |
testcase_31 | AC | 49 ms
53,120 KB |
testcase_32 | AC | 49 ms
53,248 KB |
testcase_33 | AC | 49 ms
53,616 KB |
testcase_34 | AC | 50 ms
53,376 KB |
testcase_35 | AC | 50 ms
53,760 KB |
testcase_36 | AC | 49 ms
53,504 KB |
testcase_37 | AC | 49 ms
53,504 KB |
testcase_38 | AC | 50 ms
53,248 KB |
ソースコード
#!/usr/bin/python # -*- coding: utf-8 -*- # import from sys import stdin, setrecursionlimit setrecursionlimit(10**8) # def def int_map(): return map(int,input().split()) def int_list(): return ['Null']+list(map(int,input().split())) # 整数のリストのリスト:N+1行のリスト(各行のリストは同じ長さでなくてよい.) def int_mtx(N): x = [['Null']+list(map(int, stdin.readline().split())) for _ in range(N)] x.insert(0,['Null']) return x # 文字のリストのリスト:N+1行のリスト(各行のリストは同じ長さでなくてよい.) # AAAAA # BBBBB # CCCCC # のような標準入力を # '0AAAAA' # '0BBBBB' # '0CCCCC' # と受け取る def str_mtx(N): x = ['0'+stdin.readline()[:-1] for _ in range(N)] x.insert(0,'0') return x # 文字のリストのリスト:N+1行のリスト(各行のリストは同じ長さでなくてよい.) # AAAAA XXXXX # BBBBB YYYYY # CCCCC ZZZZZ # のような標準入力を # [[['0'],[AAAAA],[XXXXX]], # [['0'],[BBBBB],[YYYYY]], # [['0'],[CCCCC],[ZZZZZ]] ] # と受け取る def str_list(N): x = [['0']+list(map(str, stdin.readline().split())) for _ in range(N)] x.insert(0,['0']) return x # 高さH+1, 幅W+1, のゼロ行列の作成 def zero_mtx(H,W): x = [[0]*(W+1) for i in range(H+1)] return x # リストをスペースで分割する(先頭を省く) def print_space(l): return print(" ".join([str(x) for x in l[1:]])) # ゼロインデックスの場合 # 整数のリストのリスト:N行のリスト(各行のリストは同じ長さでなくてよい.) def int_mtx_0(N): x = [list(map(int, stdin.readline().split())) for _ in range(N)] return x # ゼロインデックスの場合 # 文字のリストのリスト:N+1行のリスト(各行のリストは同じ長さでなくてよい.) def str_mtx_0(N): x = [list(stdin.readline()[:-1]) for _ in range(N)] return x # ゼロインデックスの場合 # リストをスペースで分割する(先頭を省かない) def print_space_0(l): return print(" ".join([str(x) for x in l])) # ゼロインデックスの場合 # 高さH, 幅W, のゼロ行列の作成 def zero_mtx_0(H,W): x = [[0]*W for i in range(H)] return x def int_list_0(): return list(map(int,input().split())) ## インポート # from collections import deque # 順列に使う # import itertools # 最大公約数などに使う # import math # リストの要素の数をdict形式で # import collections # 二次元配列のコピーを作りたいとき # a_copy = deepcopy(a) # from copy import deepcopy # main code N,M = int_map() ABCX = int_mtx_0(M) """ ダイクストラ法(ヒープによる優先度付きキューを用いて) 計算量 O( |E|*log(|V|)) E:辺の数 V:頂点数 ベルマンフォードより早いが,負のコストがあると使えない. """ import heapq def dijkstra(edges, start_id): num_node = len(edges) c0 = [float('INF')]*num_node c1 = [float('INF')]*num_node c0[start_id] = 0 #スタートは0で初期化 visit = [0]*num_node candidate0 = [] candidate1 = [] heapq.heappush(candidate0, [0, start_id]) while len(candidate0)>0 or len(candidate1)>0: if len(candidate0) == 0: _, min_point = heapq.heappop(candidate1) #経路の要素を各変数に格納することで,視覚的に見やすくする for factor in edges[min_point]: goal = factor[0] #終点 cost = factor[1] #コスト x = factor[2] # 動物がいるかどうか if c1[min_point] + cost < c1[goal]: c1[goal] = c1[min_point] + cost heapq.heappush(candidate1, [c1[goal], goal]) elif len(candidate1) == 0: _, min_point = heapq.heappop(candidate0) #経路の要素を各変数に格納することで,視覚的に見やすくする for factor in edges[min_point]: goal = factor[0] #終点 cost = factor[1] #コスト x = factor[2] # 動物がいるかどうか if x == 0: if c0[min_point] + cost < c0[goal]: c0[goal] = c0[min_point] + cost heapq.heappush(candidate0, [c0[goal], goal]) else: if c0[min_point] + cost < c1[goal]: c1[goal] = c0[min_point] + cost heapq.heappush(candidate1, [c1[goal], goal]) else: if candidate0[0][0] <= candidate1[0][0]: _, min_point = heapq.heappop(candidate0) #経路の要素を各変数に格納することで,視覚的に見やすくする for factor in edges[min_point]: goal = factor[0] #終点 cost = factor[1] #コスト x = factor[2] # 動物がいるかどうか if x == 0: if c0[min_point] + cost < c0[goal]: c0[goal] = c0[min_point] + cost heapq.heappush(candidate0, [c0[goal], goal]) else: if c0[min_point] + cost < c1[goal]: c1[goal] = c0[min_point] + cost heapq.heappush(candidate1, [c1[goal], goal]) else: _, min_point = heapq.heappop(candidate1) #経路の要素を各変数に格納することで,視覚的に見やすくする for factor in edges[min_point]: goal = factor[0] #終点 cost = factor[1] #コスト x = factor[2] # 動物がいるかどうか if c1[min_point] + cost < c1[goal]: c1[goal] = c1[min_point] + cost heapq.heappush(candidate1, [c1[goal], goal]) return c1 start_id = N-1 # UVC = [ [始点1,終点1,コスト1], ..., [始点M,終点M,コストM] ] UVC = [] for i in range(M): UVC.append([ABCX[i][0]-1, ABCX[i][1]-1, ABCX[i][2], ABCX[i][3]]) Di = False Edges = [[] for _ in range(N)] if Di: for ui, vi, ci in UVC: Edges[ui].append([vi,ci]) else: for ui, vi, ci, xi in UVC: Edges[ui].append([vi,ci,xi]) Edges[vi].append([ui,ci,xi]) opt = dijkstra(Edges, start_id) for i in range(N-1): print(opt[i])