結果

問題 No.468 役に立つ競技プログラミング実践編
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 525 ms / 2,000 ms
コード長 1,767 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,256 KB
実行使用メモリ 167,292 KB
最終ジャッジ日時 2025-03-20 21:17:49
合計ジャッジ時間 8,980 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 31
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

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

    in_edges = [[] for _ in range(N)]
    out_edges = [[] for _ in range(N)]
    indegree = [0] * N

    for _ in range(M):
        A = int(input[ptr])
        ptr += 1
        B = int(input[ptr])
        ptr += 1
        C = int(input[ptr])
        ptr += 1
        in_edges[B].append((A, C))
        out_edges[A].append((B, C))
        indegree[B] += 1

    # Kahn's algorithm for topological sort
    queue = deque()
    for i in range(N):
        if indegree[i] == 0:
            queue.append(i)
    topo_order = []
    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for (v, _) in out_edges[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # Calculate earliest times
    earliest = [0] * N
    for u in topo_order:
        max_e = 0
        for (a, c) in in_edges[u]:
            current = earliest[a] + c
            if current > max_e:
                max_e = current
        earliest[u] = max_e

    T = earliest[N - 1]

    # Calculate latest times
    latest = [float('inf')] * N
    latest[N - 1] = T
    for u in reversed(topo_order):
        if u == N - 1:
            continue
        min_l = float('inf')
        for (v, c) in out_edges[u]:
            candidate = latest[v] - c
            if candidate < min_l:
                min_l = candidate
        latest[u] = min_l

    # Count critical nodes
    critical = 0
    for i in range(N):
        if earliest[i] == latest[i]:
            critical += 1

    P = N - critical
    print(f"{T} {P}/{N}")

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