結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:41:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,026 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 81,808 KB |
実行使用メモリ | 134,904 KB |
最終ジャッジ日時 | 2023-10-19 12:13:56 |
合計ジャッジ時間 | 16,556 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
79,852 KB |
testcase_01 | AC | 89 ms
79,848 KB |
testcase_02 | AC | 88 ms
79,848 KB |
testcase_03 | AC | 87 ms
79,844 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 89 ms
79,852 KB |
testcase_07 | WA | - |
testcase_08 | AC | 132 ms
83,828 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 128 ms
83,176 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 233 ms
108,440 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 205 ms
94,992 KB |
testcase_24 | AC | 150 ms
88,760 KB |
testcase_25 | AC | 283 ms
100,036 KB |
testcase_26 | AC | 401 ms
108,300 KB |
testcase_27 | AC | 285 ms
100,720 KB |
testcase_28 | AC | 233 ms
94,572 KB |
testcase_29 | AC | 290 ms
100,712 KB |
testcase_30 | AC | 243 ms
96,004 KB |
testcase_31 | AC | 218 ms
95,260 KB |
testcase_32 | AC | 225 ms
99,004 KB |
testcase_33 | AC | 359 ms
106,384 KB |
testcase_34 | AC | 389 ms
106,368 KB |
testcase_35 | AC | 401 ms
115,496 KB |
testcase_36 | AC | 387 ms
111,404 KB |
testcase_37 | AC | 211 ms
99,296 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 215 ms
116,004 KB |
testcase_44 | AC | 228 ms
126,672 KB |
testcase_45 | AC | 176 ms
98,468 KB |
testcase_46 | AC | 135 ms
110,464 KB |
testcase_47 | AC | 87 ms
79,932 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]: D[vi]+=(D[ui]+D2[ui]*li)*ai%mod D2[vi]+=D2[ui]*ai D2[vi]%=mod qq=[0] D3=[0]*(n+1) D3[0]=1 while qq: uk=qq.pop() for vk,_,_ in G[uk]: if D3[vk]: continue D3[vk]=1 qq+=[vk] if not D2[n] and D3[n]: print("INF") else: print(D[n])