이번 문제는 BFS를 통해 해결하였다. 도로가 모두 일방통행이므로 정방향에 대한 도로의 정보를 인접 리스트로 저장하고, 역방향에 대한 도로의 정보를 인접 리스트로 저장하였다. 그리고 도로의 정방향에 대하여 BFS를 통해 탐색하며 비용을 저장하는 리스트 costs를 최댓값으로 갱신한다. 그리고 역방향에 대하여 BFS를 통해 탐색하며 다음 노드와 현재 노드의 costs값 차가 현재 저장된 cost와 같을 경우 방문 도로의 갯수를 세는 변수 cnt를 증가시킨다. 그리고 다음 노드에 대한 중복을 막기 위해 chk리스트로 표시주었다.

Code

from collections import deque
n = int(input())
m = int(input())
roads = [[] for _ in range(n+1)]
back_roads = [[] for _ in range(n+1)]
city = [0 for _ in range(n+1)]
costs = [0 for _ in range(n+1)]
chk = [False for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    roads[a].append((b, c))
    back_roads[b].append((a, c))
    city[b] += 1
start, end = map(int, input().split())
def bfs():
    q = deque()
    q.append(start)
    while q:
        cur = q.popleft()
        for nxt, cost in roads[cur]:
            city[nxt] -= 1
            costs[nxt] = max(costs[nxt], costs[cur]+cost)
            if city[nxt] == 0:
                q.append(nxt)
    cnt = 0
    q.append(end)
    while q:
        cur = q.popleft()
        for nxt, cost in back_roads[cur]:
            if costs[cur]-costs[nxt] == cost:
                cnt += 1
                if not chk[nxt]:
                    chk[nxt] = True
                    q.append(nxt)
    return cnt
cnt = bfs()
answer = costs[end]
print(answer)
print(cnt)