# 1948 임계경로

문제 :<https://www.acmicpc.net/problem/1948>

```python
import sys
sys.setrecursionlimit(10**5)
# 해당 도시까지 걸리는 최대 시간 경로 갱신
def max_time(city):
    if city==start:
        return 0
    if time[city]==-1: # 아직 탐색하지 않았다면
        for s,t in graph[city]:
            bef_time = max_time(s)+t
            if time[city] < bef_time: # 최대 경로가 갱신됐다면
                time[city] = bef_time
                course[city] = [s]
            elif time[city] == bef_time: # 최대 경로를 더 발견했다면
                time[city] = bef_time
                course[city].append(s)
    return time[city]

import sys
input = sys.stdin.readline
n=int(input()) # 도시의 개수
m=int(input()) # 도로의 개수
time=[-1]*(n+1) # 도시 도착 최대 시간
course=[[] for _ in range(n+1)]
graph=[[] for _ in range(n+1)] # 각 도시로 향하는 경로
# 도로 정보 받기
for _ in range(m):
    s,a,t = map(int,input().split())
    graph[a].append((s,t))
start,arrive=map(int,input().split())

print(max_time(arrive))
from collections import deque
result=set()
q=deque()
q.append(arrive)
while q:
    city=q.popleft()
    for bef in course[city]:
        if (bef,city) not in result:
            result.add((bef,city))
            q.append(bef)
print(len(result))
```

**경로 역추적**에 대한 아이디어 얻어가기.

굳이 정점에 이전까지의 모든 경로를 저장하지 않아도 될 때가 있다.

특정 조건을 만족하는 이전 정점 하나만 저장하고 마지막에 한 번만 따라가면 됨.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/1948.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.