Submission #6826245

---

Source Code Expand

#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        a, b = value
        heapq.heappush(self.heap, (-a, b))

    def pop(self):
        a, b = heapq.heappop(self.heap)
        return -a, b

    def __len__(self):
        return len(self.heap)


# 有効グラフを仮定する。
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 solve(N: int, M: int, P: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    for i in range(M):
        C[i] -= P

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

    longest = [0]*N
    visited = [False]*N
    q = MaxHeap([])
    q.push([0, 0])
    while len(q) > 0:
        node, dist = q.pop()
        visited[node] = True
        for to_, coin in g.E[node]:
            if longest[node] == INF and longest[to_] != INF:
                visited[to_] = False
            if visited[to_] is False:
                longest[to_] = dist+coin
                q.push([to_, dist+coin])
            else:
                if longest[to_] < dist+coin:
                    longest[to_] = INF
                    q.push([to_, INF])

    if longest[N-1] == INF:
        print(-1)
    else:
        print(max(longest[N-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

Judge Result