結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:32:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,926 bytes |
コンパイル時間 | 816 ms |
コンパイル使用メモリ | 81,500 KB |
実行使用メモリ | 132,744 KB |
最終ジャッジ日時 | 2023-10-19 12:04:01 |
合計ジャッジ時間 | 20,367 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 135 ms
79,908 KB |
testcase_01 | AC | 127 ms
79,844 KB |
testcase_02 | AC | 120 ms
79,876 KB |
testcase_03 | AC | 123 ms
79,848 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 116 ms
79,872 KB |
testcase_07 | WA | - |
testcase_08 | AC | 172 ms
83,820 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 173 ms
83,208 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 296 ms
107,900 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 264 ms
94,616 KB |
testcase_24 | AC | 191 ms
88,720 KB |
testcase_25 | AC | 318 ms
99,148 KB |
testcase_26 | AC | 428 ms
107,796 KB |
testcase_27 | AC | 357 ms
100,552 KB |
testcase_28 | AC | 273 ms
94,288 KB |
testcase_29 | AC | 361 ms
100,520 KB |
testcase_30 | AC | 276 ms
94,248 KB |
testcase_31 | AC | 269 ms
94,900 KB |
testcase_32 | AC | 275 ms
96,424 KB |
testcase_33 | AC | 437 ms
104,308 KB |
testcase_34 | AC | 445 ms
106,048 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 275 ms
99,260 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 253 ms
115,260 KB |
testcase_44 | AC | 266 ms
118,752 KB |
testcase_45 | AC | 214 ms
97,528 KB |
testcase_46 | WA | - |
testcase_47 | AC | 114 ms
79,936 KB |
ソースコード
from collections import defaultdict, deque, Counter from heapq import heappush, heappop, heapify import math import bisect import random from itertools import permutations, accumulate, combinations, product import sys import string from bisect import bisect_left, bisect_right from math import factorial, ceil, floor from operator import mul from functools import reduce import pprint sys.setrecursionlimit(10 ** 9) INF = 10 ** 20 def LI(): return list(map(int, sys.stdin.readline().split())) def I(): return int(sys.stdin.readline()) def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split() def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8') def IR(n): return [I() for i in range(n)] def LIR(n): return [LI() for i in range(n)] def SR(n): return [S() for i in range(n)] def LSR(n): return [LS() for i in range(n)] def SRL(n): return [list(S()) for i in range(n)] def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)] mod = 10**9+7 n,m=LI() G=[[]for _ in range(n+1)] for _ in range(m): u,v,l,a=LI() G[u]+=[(v,l,a)] def topological_sort(G): n = len(G) in_degree = [0] * n for u in range(n): for v,_,_ in G[u]: in_degree[v] += 1 topological_order = [] que = deque() for i in range(n): if in_degree[i] == 0: que += [i] while que: u = que.pop() topological_order += [u] for v,_,_ in G[u]: in_degree[v] -= 1 if in_degree[v] == 0: que += [v] return topological_order q=deque([0]) D=[0]*(n+1) D2=[0]*(n+1) D2[0]=1 D[0]=0 order=topological_sort(G) s=set() for ui in order: s.add(ui) for vi,li,ai in G[ui]: if vi in s: print("INF") exit() D[vi]+=(D[ui]+D2[ui]*li)*ai%mod D2[vi]+=D2[ui]*ai D2[vi]%=mod if not D2[n]: print("INF") exit() print(D[n])