최단 경로
면접 대비시간 제한1초메모리 제한256 MB
정점 20,000개, 간선 300,000개인 방향 그래프에서 시작점 K로부터 각 정점까지 최단 거리를 구하고 도달 불가능하면 INF를 출력합니다.
문제
방향 그래프와 시작 정점 K가 주어진다. K에서 각 정점까지 가는 최단 거리를 구하시오. 모든 간선의 가중치는 1 이상 10 이하의 정수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. 제한은 1 <= V <= 20,000, 1 <= E <= 300,000이다. 정점 번호는 1부터 V까지이다.
둘째 줄에 시작 정점 K가 주어진다. 1 <= K <= V이다.
다음 E개의 줄에는 간선 하나를 나타내는 정수 u, v, w가 주어진다. 이는 u에서 v로 가는 가중치 w의 방향 간선이 있다는 뜻이다. u와 v는 서로 다르며, w는 1 이상 10 이하의 정수이다. 같은 순서의 두 정점 사이에 간선이 여러 개 있을 수 있다.
출력
총 V줄을 출력한다. i번째 줄에는 K에서 i번 정점까지의 최단 거리를 출력한다. 시작 정점 자신은 0을 출력한다. K에서 도달할 수 없는 정점은 INF를 출력한다.