結果

問題 No.1364 [Renaming] Road to Cherry from Zelkova
ユーザー lam6er
提出日時 2025-03-20 20:53:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 625 ms / 2,500 ms
コード長 4,597 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 196,064 KB
最終ジャッジ日時 2025-03-20 20:53:26
合計ジャッジ時間 18,611 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 10**9 + 7

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1

    edges = []
    for _ in range(M):
        u = int(input[idx])
        v = int(input[idx+1])
        l = int(input[idx+2])
        a = int(input[idx+3])
        edges.append((u, v, l, a))
        idx += 4

    # Step 1: Compute S (0-reachable)
    adj_forward = [[] for _ in range(N+1)]
    for u, v, _, _ in edges:
        adj_forward[u].append(v)

    S = [False] * (N + 1)
    q = deque()
    q.append(0)
    S[0] = True
    while q:
        u = q.popleft()
        for v in adj_forward[u]:
            if not S[v]:
                S[v] = True
                q.append(v)

    # Step 2: Compute T (N-reachable in reverse graph)
    adj_backward = [[] for _ in range(N+1)]
    for u, v, _, _ in edges:
        adj_backward[v].append(u)

    T = [False] * (N + 1)
    q = deque()
    q.append(N)
    T[N] = True
    while q:
        u = q.popleft()
        for v in adj_backward[u]:
            if not T[v]:
                T[v] = True
                q.append(v)

    # Step 3: Build partial graph (u in S and v in T)
    partial_edges = []
    adj_partial = [[] for _ in range(N+1)]
    for u, v, l, a in edges:
        if S[u] and T[v]:
            adj_partial[u].append(v)
            partial_edges.append((u, v, l, a))

    # Check if there's any path from 0 to N
    visited = [False] * (N + 1)
    q = deque()
    q.append(0)
    visited[0] = True
    reach_N = False
    while q:
        u = q.popleft()
        if u == N:
            reach_N = True
            break
        for v in adj_partial[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
    if not reach_N:
        print(0)
        return

    # Step 4: Build adjacency and reverse adjacency for partial graph
    adj_part = [[] for _ in range(N+1)]
    rev_adj_part = [[] for _ in range(N+1)]
    for u, v, l, a in partial_edges:
        adj_part[u].append(v)
        rev_adj_part[v].append(u)

    # Kosaraju's algorithm to find SCCs in partial graph
    visited = [False] * (N+1)
    order = []

    # First pass to get finishing order
    for u in range(N+1):
        if S[u] and any(T[v] for v in adj_partial[u]) and not visited[u]:
            stack = [(u, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append((node, True))
                for v in reversed(adj_part[node]):
                    if not visited[v]:
                        stack.append((v, False))

    # Second pass to get components
    visited = [False] * (N+1)
    components = []
    for node in reversed(order):
        if not visited[node]:
            stack = [node]
            visited[node] = True
            component = [node]
            while stack:
                u = stack.pop()
                for v in rev_adj_part[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
                        component.append(v)
            components.append(component)

    # Check if any component has size >=2
    for component in components:
        if len(component) >= 2:
            print("INF")
            return

    # Step 5: Topological sort on partial graph
    edge_info = [[] for _ in range(N+1)]
    for u, v, l, a in partial_edges:
        edge_info[u].append((v, l, a))

    in_degree = [0] * (N+1)
    for u in range(N+1):
        for v, _, _ in edge_info[u]:
            in_degree[v] += 1

    q = deque()
    for u in range(N+1):
        if in_degree[u] == 0 and S[u] and T[u]:
            q.append(u)
    topo_order = []

    while q:
        u = q.popleft()
        topo_order.append(u)
        for v, _, _ in edge_info[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)

    # Step 6: Dynamic Programming
    dp_num = [0] * (N + 1)
    dp_sum = [0] * (N + 1)
    dp_num[0] = 1

    for u in topo_order:
        for v, l, a in edge_info[u]:
            ways = dp_num[u] * a % MOD
            sum_val = (dp_sum[u] * a + dp_num[u] * a % MOD * l) % MOD
            dp_num[v] = (dp_num[v] + ways) % MOD
            dp_sum[v] = (dp_sum[v] + sum_val) % MOD

    print(dp_sum[N] % MOD)

if __name__ == "__main__":
    main()
0