洛谷1807-最长路-python-(拓扑排序+dp)

AC代码

n,m=map(int,input().split())
if m==0:
    print(-1)
else:
    side=[0]*m
    point=[[] for i in range(n+1)]

    rud=[0]*(n+1)
    dp=[-float("inf")]*(n+1)
    for i in range(m):
        side[i]=list(map(int,input().split()))
        point[side[i][0]].append(i)
        rud[side[i][1]]+=1

    queue=[]
    for i in range(1,n+1):
        if rud[i]==0:
            queue.append(i)
    dp[1]=0
    while len(queue)!=0:
        fr=queue.pop(0)
        for i in range(len(point[fr])):
            s=point[fr][i]
            p=side[s][1]
            
            dp[p]=max(dp[p],dp[fr]+side[s][2])
            
            rud[p]-=1
            if rud[p]==0:
                queue.append(p)
    if dp[n]==-float("inf"):
        print(-1)
    else:
        print(dp[n])