Submission #6839849


Source Code Expand

Copy
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")


# 有効グラフを仮定する。
class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def BellmanFord(g: Graph, s):
    """ベルマンフォード法による最短経路
    """
    N = g.N
    dist = [INF]*N
    dist[s] = 0
    prev = [None]*N

    # 辺の緩和
    for _ in range(N):
        for from_ in range(N):      # ここの2重ループはO(M)
            for to_, weight in g.E[from_]:
                if dist[to_] > dist[from_] + weight:
                    dist[to_] = dist[from_] + weight
                    prev[to_] = from_
    # 負の重みの閉路がないかチェック
    for from_ in range(N):
        for to_, weight in g.E[from_]:
            if dist[from_]+weight < dist[to_]:
                return None, None

    return dist, prev


def solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    for i in range(M):
        C[i] = P - C[i]

    rev_g = Graph(N)
    for a, b, c in zip(A, B, C):
        rev_g.add_edge([b-1, a-1, c])

    # Nに到達できないノードは除く
    visitable = [False]*N
    visitable[N-1] = True
    q = deque()
    q.append(N-1)
    while len(q) > 0:
        curr = q.popleft()
        for t_, w in rev_g.E[curr]:
            if not visitable[t_]:
                visitable[t_] = True
                q.append(t_)

    g = Graph(N)
    for a, b, c in zip(A, B, C):
        if visitable[a-1] and visitable[b-1]:
            g.add_edge([a-1, b-1, c])

    dist, prev = BellmanFord(g, 0)
    if dist is None:
        print(-1)
    else:
        print(max(-dist[-1], 0))

    # print(longest)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, P, A, B, C)


if __name__ == '__main__':
    main()

Submission Info

Submission Time
Task E - Coins Respawn
User toot_tatsuhiro
Language PyPy3 (2.4.0)
Score 500
Code Size 2876 Byte
Status AC
Exec Time 1107 ms
Memory 53468 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 56
Set Name Test Cases
Sample a01, a02, a03
All a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55, b56
Case Name Status Exec Time Memory
a01 AC 170 ms 38256 KB
a02 AC 166 ms 38256 KB
a03 AC 167 ms 38256 KB
b04 AC 172 ms 38256 KB
b05 AC 168 ms 38256 KB
b06 AC 164 ms 38256 KB
b07 AC 164 ms 38256 KB
b08 AC 167 ms 38256 KB
b09 AC 676 ms 46684 KB
b10 AC 670 ms 47216 KB
b11 AC 687 ms 46172 KB
b12 AC 533 ms 52444 KB
b13 AC 531 ms 52444 KB
b14 AC 658 ms 46044 KB
b15 AC 217 ms 44252 KB
b16 AC 214 ms 44252 KB
b17 AC 214 ms 44252 KB
b18 AC 664 ms 46940 KB
b19 AC 670 ms 47068 KB
b20 AC 667 ms 48268 KB
b21 AC 683 ms 46812 KB
b22 AC 222 ms 43868 KB
b23 AC 225 ms 43868 KB
b24 AC 525 ms 45916 KB
b25 AC 186 ms 39664 KB
b26 AC 986 ms 49372 KB
b27 AC 986 ms 49244 KB
b28 AC 996 ms 48860 KB
b29 AC 987 ms 50652 KB
b30 AC 968 ms 49500 KB
b31 AC 985 ms 49116 KB
b32 AC 919 ms 50268 KB
b33 AC 946 ms 49244 KB
b34 AC 836 ms 49756 KB
b35 AC 796 ms 50524 KB
b36 AC 903 ms 49500 KB
b37 AC 766 ms 49756 KB
b38 AC 714 ms 49756 KB
b39 AC 705 ms 49116 KB
b40 AC 644 ms 49628 KB
b41 AC 601 ms 49244 KB
b42 AC 260 ms 45660 KB
b43 AC 1008 ms 52828 KB
b44 AC 1035 ms 53468 KB
b45 AC 972 ms 52804 KB
b46 AC 1107 ms 51932 KB
b47 AC 751 ms 49372 KB
b48 AC 223 ms 43868 KB
b49 AC 670 ms 46940 KB
b50 AC 704 ms 50524 KB
b51 AC 679 ms 46428 KB
b52 AC 706 ms 50524 KB
b53 AC 667 ms 46812 KB
b54 AC 523 ms 45916 KB
b55 AC 978 ms 48348 KB
b56 AC 1013 ms 49372 KB