도로 추가 조회 후 최단 거리 I

3243. 도로 추가 조회 후 최단 거리 I

난이도:중

주제: 배열, 너비 우선 검색, 그래프

정수 n과 2차원 정수 배열 쿼리가 제공됩니다.

0부터 n - 1까지 번호가 매겨진 n개의 도시가 있습니다. 처음에는 도시 i에서 도시 i까지 단방향 도로가 있습니다. 모두 0 <= i < n - 1.

queries[i] = [u_i, v_i]는 도시 ui<🎜에서 새로운 단방향 _{도로 추가를 나타냅니다. > v}i _{도시로. 각 쿼리 후에는 도시 0에서 도시 n - 1까지의} 최단 경로의 길이를 찾아야 합니다.

반환

[0, query.length - 1] 범위의 각 i에 대해 답변[i]가 <를 처리한 후 도시 0에서 도시 n - 1까지의 최단 경로 길이인 배열 답변을 반환합니다. 🎜>첫 번째 검색어 1개.

예 1:

입력:
• n = 5, 쿼리 = [[2,4],[0,2],[0,4]]
출력:
• [3,2,1]
설명:
• 2에서 4까지의 도로를 추가한 후 0에서 4까지의 최단 경로의 길이는 3이 됩니다. 0에서 2까지의 도로를 추가한 후, 0에서 4까지의 최단 경로의 길이는 2가 됩니다. 0에서 4까지의 도로를 추가한 후 0에서 4까지의 최단 경로의 길이는 1이 됩니다.

예 2:

입력:
• n = 4, 쿼리 = [[0,3],[0,2]]
출력:
• [1,1]
설명:
• 0에서 3까지 도로를 추가한 후 0에서 3까지의 최단 경로 길이는 1이 됩니다. 0에서 2까지 도로를 추가하면 최단 경로의 길이는 1로 유지됩니다.

제약조건:

3 <= n <= 500

• 1 <= query.length <= 500
• 쿼리[i].length == 2
• 0 <= 검색어[i][0] < 쿼리[i][1] < ㄴ
• 1 < 쿼리[i][1] - 쿼리[i][0]
• 쿼리 중 반복되는 도로는 없습니다.

힌트:

1. 각 업데이트 후에 그래프를 유지하고 효율적인 최단 경로 알고리즘을 사용합니다.
2. 각 쿼리에는 BFS/Dijkstra를 사용합니다.

해결책:

도시 간 도로 추가를 시뮬레이션하고 각 도로 추가 후 도시 0에서 도시 n - 1까지의 최단 경로를 계산해야 합니다. 제약 조건과 문제의 성격을 고려하여 비가중 그래프에 BFS(너비 우선 검색)를 사용할 수 있습니다.

접근하다:

1. 그래프 표현:

   • 인접 목록을 사용하여 도시와 도로를 나타낼 수 있습니다. 처음에, 각 도시 i는 모든 0 <= i <에 대해 도시 i로 가는 도로를 갖게 됩니다. n - 1.
   • 각 쿼리 후에 u_i에서 v_i까지의 도로를 그래프에 추가합니다.

2. 최단 경로 계산(BFS):

   • BFS를 사용하여 도시 0에서 도시 n - 1까지의 최단 경로를 계산할 수 있습니다. 모든 도로의 가중치가 동일하기 때문에(각 도로의 길이는 1임) BFS가 여기서 잘 작동합니다.

3. 쿼리 반복:

   • 각 쿼리에 대해 그래프에 새 도로를 추가한 다음 BFS를 사용하여 도시 0에서 도시 n - 1까지의 최단 경로를 찾습니다. 각 쿼리를 처리한 후 결과를 출력 배열에 저장합니다.

4. 효율성:

   • 각 쿼리 후에 BFS를 사용하고 그래프 크기는 최대 500개의 도시, 최대 500개의 쿼리가 될 수 있으므로 각 BFS의 시간 복잡도는 O(n·m)입니다. 여기서 n은 도시의 수이고 m은 도로의 수. BFS를 최대 500회까지 수행해야 솔루션이 문제의 제약 조건 내에서 효율적으로 실행됩니다.

이 솔루션을 PHP로 구현해 보겠습니다: 3243. 도로 추가 조회 후 최단 거리 I

  
  
  설명:




그래프 초기화:


인접 목록 그래프를 사용하여 도시와 도로를 표현합니다.
처음에는 연속된 도시(i~i 1) 사이에만 도로가 존재합니다.



BFS 기능:


BFS는 도시 0에서 도시 n - 1까지의 최단 거리를 계산하는 데 사용됩니다. BFS에 대한 대기열과 각 도시에 도달하는 최소 도로(가장자리) 수를 저장하는 거리 배열을 유지합니다.
처음에는 0번 도시까지의 거리가 0으로 설정되어 있고, 그 외 모든 도시의 거리는 무한대(PHP_INT_MAX)입니다.
BFS 대기열의 각 도시를 처리하면서 인접 도시의 거리를 업데이트하고 도달 가능한 모든 도시를 방문할 때까지 계속합니다.



쿼리 처리:


각 쿼리에 대해 새 도로가 그래프에 추가됩니다(u -> v).
업데이트 후 도시 0에서 도시 n-1까지의 최단 경로를 계산하기 위해 BFS가 호출됩니다.
BFS의 결과는 결과 배열에 저장됩니다.



출력:

결과 배열에는 각 쿼리 후 가장 짧은 경로 길이가 포함됩니다.



시간 복잡도:


각 BFS는 O(n·m)을 차지합니다. 여기서 n은 도시 수이고 m은 도로 수입니다. 쿼리 수가 q개이므로 전체 시간 복잡도는 O(q * (n m))이며 이는 주어진 제약 조건에 효율적입니다.





  
  
  예제 연습:


입력 n = 5 및 쿼리 = [[2, 4], [0, 2], [0, 4]]:


처음에는 도로가 [0 -> 1 -> 2 -> 3 -> 4].
첫 번째 쿼리 [2, 4] 이후 도로는 [0 -> 1 -> 2 -> 3 -> 4]이고 0에서 4까지의 최단 경로는 3입니다(경로 0 -> 1 -> 2 -> 4 사용).
두 번째 쿼리 [0, 2] 이후 도로는 [0 -> 2, 1 -> 2 -> 3 -> 4], 0에서 4까지의 최단 경로는 2입니다(경로 0 -> 2 -> 4 사용).
세 번째 쿼리 [0, 4] 이후 도로는 [0 -> 2, 1 -> 2 -> 3 -> 4], 0에서 4까지의 최단 경로는 1(직통 도로 0 -> 4)입니다.


따라서 출력은 [3, 2, 1]입니다.


  
  
  최종 생각:



이 솔루션은 각 쿼리에 BFS를 사용하여 최단 경로를 효율적으로 계산합니다.
각 쿼리에 새로운 도로가 추가될 때마다 그래프가 동적으로 업데이트됩니다.
이 솔루션은 문제의 제약 내에서 잘 작동하며 최대 500개 도시에 대한 최대 500개의 쿼리를 효율적으로 처리합니다.


연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 도로 추가 조회 후 최단 거리 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!