코딩테스트 연습 - 중요한 도로 | 프로그래머스 스쿨

문제 설명

현대모비스의 자율주행 시스템은 출발지와 목적지를 입력하면 목적지에 도착하기까지의 가장 빠른 예상 소요 시간을 알려줍니다. 자율주행 시스템은 도시 내에 있는 n개의 지점을 연결하는 양방향 도로 m개의 교통량을 분석해서 예상 소요 시간을 실시간으로 계산합니다. 만약 어떤 도로의 길이가 L이고 교통량이 T라면 해당 도로를 통과하는데 L + T분이 소요됩니다. (0 ≤ T)

다음은 n = 5, m = 7인 예시입니다.

원은 지점을 나타내며, 원에 적힌 수는 지점의 번호입니다. 항상 1번 지점이 출발지, n번 지점이 목적지입니다.
선분은 지점을 연결하는 도로를 나타내며, 선분 옆에 적힌 수는 [#도로 번호] 길이/교통량을 의미합니다.
목적지에 도착하기까지의 가장 빠른 예상 소요 시간은 1-2-4-5와 같이 이동했을 때 20(= 10 + 8 + 2)분입니다.

이때 7번 도로의 교통량이 3 증가한다고 가정해 보겠습니다.

목적지에 도착하기까지의 가장 빠른 예상 소요 시간은 1-2-5와 같이 이동했을 때 22(= 10 + 12)분으로, 교통량이 변하기 전에 비해 2분 증가했습니다.

7번 도로 대신 2번 도로의 교통량이 2 증가한다고 가정해 보겠습니다.

목적지에 도착하기까지의 가장 빠른 예상 소요 시간은 1-3-4-5와 같이 이동했을 때 20(= 9 + 9 + 2)분으로, 교통량이 변하기 전과 같습니다.

2, 7번 도로 대신 5번 도로의 교통량이 6 감소한다고 가정해 보겠습니다.

목적지에 도착하기까지의 가장 빠른 예상 소요 시간은 1-3-5와 같이 이동했을 때 19(= 10 + 9)분으로, 교통량이 변하기 전에 비해 1분 감소했습니다.

모든 도로의 교통량 정보를 실시간으로 업데이트하는 것은 비효율적이기 때문에, 위와 같이 한 도로의 교통량이 변했을 때 가장 빠른 예상 소요 시간이 변할 수 있는 도로(5, 7번 도로)에 대해서만 실시간으로 교통량 정보를 업데이트해야 합니다.

지점의 수를 나타내는 정수 n과 도로의 정보를 나타내는 2차원 정수 배열 roads가 매개변수로 주어집니다. 이때 한 도로의 교통량이 변했을 때 1번 지점에서 출발해 n번 지점에 도착하는 가장 빠른 예상 소요 시간이 변할 수 있는 도로의 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 만약 그러한 도로가 없다면 [-1]을 return 합니다.

제한사항

2 ≤ n ≤ 50,000
- 1번 지점이 출발지, n번 지점이 목적지입니다.
n - 1 ≤ roads의 길이 = m ≤ 200,000
- roads[i]는 i+1번 도로에 대한 정보를 담고 있으며 [U, V, L, T] 형태의 길이가 4인 1차원 정수 배열입니다.
- U번 지점과 V번 지점을 연결하는 길이 L, 교통량 T인 도로를 의미합니다.
- 1 ≤ U < V ≤ n
- 1 ≤ L ≤ 10⁹
- 0 ≤ T ≤ 10⁹
- 서로 다른 두 지점을 직접 연결하는 도로는 최대 1개입니다.
- 도로를 통해 한 지점에서 다른 지점으로 이동하는 방법이 항상 존재합니다.

입출력 예

n	roads	result
5	[[1, 2, 10, 0], [2, 4, 8, 0], [1, 3, 9, 0], [3, 4, 9, 0], [3, 5, 10, 6], [2, 5, 10, 2], [4, 5, 2, 0]]	[5, 7]
4	[[1, 2, 10, 10], [2, 3, 10, 10], [3, 4, 10, 10]]	[1, 2, 3]
4	[[1, 2, 5, 0], [2, 4, 5, 0], [1, 3, 5, 0], [3, 4, 5, 0]]	[-1]
4	[[1, 2, 5, 0], [2, 4, 5, 0], [1, 3, 5, 0], [3, 4, 5, 0], [1, 4, 5, 5]]	[5]