結果
問題 | No.1364 [Renaming] Road to Cherry from Zelkova |
ユーザー | ophhdn |
提出日時 | 2021-08-08 11:55:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,842 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 121,344 KB |
最終ジャッジ日時 | 2024-09-19 07:28:04 |
合計ジャッジ時間 | 16,378 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 100 ms
80,128 KB |
testcase_01 | AC | 97 ms
80,640 KB |
testcase_02 | AC | 101 ms
80,512 KB |
testcase_03 | AC | 101 ms
80,768 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 100 ms
80,640 KB |
testcase_07 | WA | - |
testcase_08 | AC | 147 ms
83,840 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 151 ms
83,712 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 248 ms
99,328 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 201 ms
92,032 KB |
testcase_24 | AC | 166 ms
89,216 KB |
testcase_25 | AC | 289 ms
99,200 KB |
testcase_26 | AC | 397 ms
108,160 KB |
testcase_27 | AC | 327 ms
101,248 KB |
testcase_28 | AC | 244 ms
94,592 KB |
testcase_29 | AC | 311 ms
101,248 KB |
testcase_30 | AC | 238 ms
94,784 KB |
testcase_31 | AC | 215 ms
93,056 KB |
testcase_32 | AC | 249 ms
96,768 KB |
testcase_33 | AC | 392 ms
104,576 KB |
testcase_34 | AC | 402 ms
105,216 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 243 ms
99,456 KB |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | AC | 226 ms
103,808 KB |
testcase_44 | AC | 226 ms
104,960 KB |
testcase_45 | AC | 197 ms
98,176 KB |
testcase_46 | AC | 139 ms
95,616 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])