LAPTRINH

DAG0

from collections import deque# ===================== INPUT ===================== n, m = map(int, input().split()) adj = [[] for _ in range(n + 1)] indeg = [0] * (n + 1)for _ in range(m):    u, v, *w = map(int, input().split())    if w:        adj[u].append((v, w[0]))  # có trọng số    else:        adj[u].append((v, 1))     # mặc định w = 1    indeg[v] += 1# ===================== TOPO SORT (KAHN) ===================== q = deque() for i in range(1, n + 1):    if indeg[i] == 0:        q.append(i)topo = [] while q:    u = q.popleft()    topo.append(u)    for v, w in adj[u]:        indeg[v] -= 1        if indeg[v] == 0:            q.append(v)# Kiểm tra có phải DAG không if len(topo) < n:    print("Graph has cycle -> NOT DAG")    exit()# ===================== TEMPLATE 1: LONGEST PATH ===================== INF = float('-inf') dp_longest = [INF] * (n + 1)start = 1  # chỉnh tùy bài dp_longest[start] = 0for u in topo:    if dp_longest[u] == INF:        continue    for v, w in adj[u]:        dp_longest[v] = max(dp_longest[v], dp_longest[u] + w)# ===================== TEMPLATE 2: SHORTEST PATH ===================== INF = float('inf') dp_shortest = [INF] * (n + 1)dp_shortest[start] = 0for u in topo:    if dp_shortest[u] == INF:        continue    for v, w in adj[u]:        dp_shortest[v] = min(dp_shortest[v], dp_shortest[u] + w)# ===================== TEMPLATE 3: COUNT PATH ===================== MOD = 10**9 + 7 dp_count = [0] * (n + 1)dp_count[start] = 1for u in topo:    for v, w in adj[u]:        dp_count[v] = (dp_count[v] + dp_count[u]) % MOD# ===================== OUTPUT DEMO ===================== end = n  # chỉnh tùy bàiprint("Topo:", topo) print("Longest:", dp_longest[end]) print("Shortest:", dp_shortest[end]) print("Count:", dp_count[end])