結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 11:55:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,842 bytes |
コンパイル時間 | 957 ms |
コンパイル使用メモリ | 81,396 KB |
実行使用メモリ | 120,796 KB |
最終ジャッジ日時 | 2023-10-19 11:19:19 |
合計ジャッジ時間 | 17,448 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 105 ms
80,016 KB |
testcase_01 | AC | 104 ms
79,996 KB |
testcase_02 | AC | 106 ms
80,020 KB |
testcase_03 | AC | 111 ms
79,984 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 106 ms
79,992 KB |
testcase_07 | WA | - |
testcase_08 | AC | 168 ms
83,712 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 156 ms
83,316 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 252 ms
99,120 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 203 ms
91,600 KB |
testcase_24 | AC | 166 ms
88,844 KB |
testcase_25 | AC | 289 ms
99,236 KB |
testcase_26 | AC | 399 ms
107,892 KB |
testcase_27 | AC | 338 ms
100,684 KB |
testcase_28 | AC | 240 ms
94,376 KB |
testcase_29 | AC | 312 ms
100,680 KB |
testcase_30 | AC | 242 ms
94,292 KB |
testcase_31 | AC | 218 ms
92,936 KB |
testcase_32 | AC | 252 ms
96,556 KB |
testcase_33 | AC | 387 ms
104,428 KB |
testcase_34 | AC | 391 ms
105,228 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 242 ms
99,396 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 230 ms
103,352 KB |
testcase_44 | AC | 233 ms
104,360 KB |
testcase_45 | AC | 198 ms
97,652 KB |
testcase_46 | AC | 141 ms
95,448 KB |
testcase_47 | WA | - |
ソースコード
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) if len(order)!=n+1: print("INF") exit() for ui in order: for vi,li,ai in G[ui]: D[vi]+=(D[ui]+D2[ui]*li)*ai%mod D2[vi]+=D2[ui]*ai D2[vi]%=mod print(D[n])