結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー ophhdnophhdn
提出日時 2021-08-08 12:44:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,882 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 81,648 KB
実行使用メモリ 134,336 KB
最終ジャッジ日時 2023-10-19 12:17:20
合計ジャッジ時間 16,962 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 104 ms
79,876 KB
testcase_01 AC 102 ms
79,884 KB
testcase_02 AC 103 ms
79,904 KB
testcase_03 AC 103 ms
79,900 KB
testcase_04 AC 105 ms
79,900 KB
testcase_05 AC 102 ms
79,896 KB
testcase_06 AC 104 ms
79,900 KB
testcase_07 AC 102 ms
79,900 KB
testcase_08 AC 154 ms
83,820 KB
testcase_09 AC 129 ms
81,108 KB
testcase_10 AC 150 ms
83,264 KB
testcase_11 AC 148 ms
83,140 KB
testcase_12 AC 141 ms
83,168 KB
testcase_13 AC 440 ms
118,036 KB
testcase_14 AC 557 ms
117,348 KB
testcase_15 AC 543 ms
122,744 KB
testcase_16 AC 433 ms
107,972 KB
testcase_17 AC 267 ms
107,900 KB
testcase_18 AC 629 ms
128,960 KB
testcase_19 AC 629 ms
132,580 KB
testcase_20 AC 639 ms
132,600 KB
testcase_21 AC 639 ms
128,700 KB
testcase_22 AC 640 ms
134,336 KB
testcase_23 AC 209 ms
91,436 KB
testcase_24 AC 172 ms
88,652 KB
testcase_25 AC 297 ms
99,052 KB
testcase_26 AC 409 ms
107,684 KB
testcase_27 AC 333 ms
100,484 KB
testcase_28 AC 243 ms
94,192 KB
testcase_29 AC 316 ms
100,480 KB
testcase_30 AC 244 ms
94,112 KB
testcase_31 AC 220 ms
92,748 KB
testcase_32 AC 252 ms
96,364 KB
testcase_33 AC 410 ms
104,248 KB
testcase_34 AC 398 ms
105,040 KB
testcase_35 WA -
testcase_36 WA -
testcase_37 AC 248 ms
99,208 KB
testcase_38 AC 327 ms
111,472 KB
testcase_39 AC 325 ms
111,500 KB
testcase_40 AC 327 ms
111,700 KB
testcase_41 AC 331 ms
111,600 KB
testcase_42 AC 327 ms
111,668 KB
testcase_43 AC 231 ms
115,204 KB
testcase_44 AC 237 ms
118,688 KB
testcase_45 AC 192 ms
97,480 KB
testcase_46 AC 150 ms
109,644 KB
testcase_47 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
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

print(D[n])
0