結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 12:43:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 620 ms / 2,500 ms |
コード長 | 2,045 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 81,824 KB |
実行使用メモリ | 133,488 KB |
最終ジャッジ日時 | 2023-10-19 12:15:13 |
合計ジャッジ時間 | 16,798 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 100 ms
79,960 KB |
testcase_01 | AC | 100 ms
79,960 KB |
testcase_02 | AC | 98 ms
79,968 KB |
testcase_03 | AC | 89 ms
79,960 KB |
testcase_04 | AC | 101 ms
79,960 KB |
testcase_05 | AC | 89 ms
79,960 KB |
testcase_06 | AC | 88 ms
79,964 KB |
testcase_07 | AC | 88 ms
79,952 KB |
testcase_08 | AC | 133 ms
83,864 KB |
testcase_09 | AC | 119 ms
81,688 KB |
testcase_10 | AC | 136 ms
83,304 KB |
testcase_11 | AC | 131 ms
83,304 KB |
testcase_12 | AC | 131 ms
83,240 KB |
testcase_13 | AC | 403 ms
118,652 KB |
testcase_14 | AC | 490 ms
117,704 KB |
testcase_15 | AC | 476 ms
123,204 KB |
testcase_16 | AC | 359 ms
108,372 KB |
testcase_17 | AC | 256 ms
108,456 KB |
testcase_18 | AC | 620 ms
129,632 KB |
testcase_19 | AC | 614 ms
133,488 KB |
testcase_20 | AC | 613 ms
133,420 KB |
testcase_21 | AC | 580 ms
129,564 KB |
testcase_22 | AC | 598 ms
132,800 KB |
testcase_23 | AC | 206 ms
95,008 KB |
testcase_24 | AC | 150 ms
88,760 KB |
testcase_25 | AC | 299 ms
100,004 KB |
testcase_26 | AC | 407 ms
108,296 KB |
testcase_27 | AC | 296 ms
100,724 KB |
testcase_28 | AC | 281 ms
94,572 KB |
testcase_29 | AC | 287 ms
100,720 KB |
testcase_30 | AC | 249 ms
96,012 KB |
testcase_31 | AC | 228 ms
95,272 KB |
testcase_32 | AC | 249 ms
99,016 KB |
testcase_33 | AC | 380 ms
106,384 KB |
testcase_34 | AC | 407 ms
106,300 KB |
testcase_35 | AC | 441 ms
115,524 KB |
testcase_36 | AC | 420 ms
111,424 KB |
testcase_37 | AC | 216 ms
99,300 KB |
testcase_38 | AC | 289 ms
111,568 KB |
testcase_39 | AC | 300 ms
111,588 KB |
testcase_40 | AC | 292 ms
111,792 KB |
testcase_41 | AC | 289 ms
111,688 KB |
testcase_42 | AC | 293 ms
111,768 KB |
testcase_43 | AC | 221 ms
116,084 KB |
testcase_44 | AC | 227 ms
126,672 KB |
testcase_45 | AC | 188 ms
98,476 KB |
testcase_46 | AC | 137 ms
110,496 KB |
testcase_47 | AC | 88 ms
79,980 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 D[vi]%=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])