結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:41:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,026 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 134,312 KB |
最終ジャッジ日時 | 2024-09-19 08:17:14 |
合計ジャッジ時間 | 18,108 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 83 ms
80,768 KB |
testcase_01 | AC | 83 ms
80,552 KB |
testcase_02 | AC | 88 ms
80,768 KB |
testcase_03 | AC | 88 ms
80,640 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 98 ms
80,688 KB |
testcase_07 | WA | - |
testcase_08 | AC | 139 ms
84,308 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 158 ms
83,712 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 284 ms
109,440 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 192 ms
95,600 KB |
testcase_24 | AC | 141 ms
89,584 KB |
testcase_25 | AC | 263 ms
100,644 KB |
testcase_26 | AC | 375 ms
108,800 KB |
testcase_27 | AC | 282 ms
101,120 KB |
testcase_28 | AC | 224 ms
95,240 KB |
testcase_29 | AC | 278 ms
101,248 KB |
testcase_30 | AC | 243 ms
96,384 KB |
testcase_31 | AC | 216 ms
95,744 KB |
testcase_32 | AC | 234 ms
99,524 KB |
testcase_33 | AC | 360 ms
107,136 KB |
testcase_34 | AC | 379 ms
106,704 KB |
testcase_35 | AC | 368 ms
116,072 KB |
testcase_36 | AC | 362 ms
112,128 KB |
testcase_37 | AC | 204 ms
99,912 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 217 ms
116,864 KB |
testcase_44 | AC | 215 ms
127,488 KB |
testcase_45 | AC | 173 ms
99,312 KB |
testcase_46 | AC | 133 ms
110,976 KB |
testcase_47 | AC | 84 ms
80,768 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])