이 문제는 컨테스트 어딘가에서 발견되어 아직 해결 방법을 찾지 못했습니다. 나는 Dijkstra를 적용하는 라인을 생각하고 있습니다. 그러나 매우 명확하지는 않습니다 :연료 제한이있는 최단 경로
''모든 가중치가있는 도시의 가중 연결된 그래프가 표시됩니다. 일부 도시 (노드)에는 휘발유 펌프가 있지만 일부는 그렇지 않습니다. 당신은 탱크 용량이 C 인 자전거를 가지고 있습니다. 즉, 탱크가 가득차 있으면 C 거리 단위로 주행 할 수 있습니다. 가솔린 펌프가 장착 된 어느 도시에서든 자동차는 탱크를 가득 채울 수 있습니다. 주어진 소스와 주어진 목적지 사이의 최단 경로를 찾으십시오. 풀 탱크로 시작한다고 가정하십시오. ''
O (mn logn)이 (가) 받아 들일 것입니다.
기본적으로 자전거가 도착했을 때 남은 연료를 기준으로 각 노드 n_i를 다중 노드 기반으로 분할해야합니다. 전화를합니다 (n_i, r). 처음에는 모두 (n_i, r)를 만들 필요가 없습니다. 비행 중에도 할 수 있습니다.
Dijkstra와 마찬가지로 노드 (n_0, C)에서 시작하여 다음 거리 (n_x, r)를 찾을 수있을 때마다 가장 작은 거리로 도달 할 수 있습니다. (n_x, r)에 연결된 모든 노드 (n_y, ry)를 업데이트합니다. ny에 펌프가 있으면 ry가 C로 재설정됩니다. 그리고 n_y에 이미 노드 (n_y, r)와 r> = ry가 있으면 새 노드 (n_y, ry)를 만들 필요가 없습니다. 무시하면됩니다.
런타임 복잡성은 말할 수 없지만 컨테스트에서 AC를 얻으려면 충분해야합니다.
(n_0, C) 다음에 어느 노드를 선택해야합니까? 각 노드마다 (distanceTravelled, n_i, r)를 저장하고 매번 최소 거리로 노드를 선택해야한다고 생각합니다. 복잡도는 (no_of_nodes * Capacity) log (no_of_nodes * Capacity) – cegprakash
@Tim Green의 방법은 노드 수인 (주유소 수에서) 지수가 이됩니다. Dijkstra를 실행하면 그 속도가 매우 느려집니다. 훨씬 빠른 방법이 있습니다.
먼저 모든 주유소 간의 거리를 찾으십시오. 또한 주유소에서 각 주유소까지의 거리, 각 주유소에서 마무리까지 그리고 출처에서 마무리까지의 거리를 포함하십시오. 이는 Dijkstra's을 여러 번 실행하여 수행 할 수 있습니다.
이렇게하면 처음부터 끝까지 유효한 모든 경로의 그래프를 얻을 수 있습니다. 이 그래프에서 Dijktra의 한 번 더 실행하여 최종 솔루션을 얻으십시오.
다 익스트라의 각 실행이 O (V 2)이 될 것이기 때문에(V = 도시의 수)하고 실행해야합니다 그것을 O (G) 시간 (G = 주유소의 수, 1 개의 주유소에서 다른 모든 주유소까지의 거리를 찾을 수 있습니다.,이 알고리즘은 O (V G) 시간으로 실행됩니다.
+1이됩니다. 그래프가 희소하지만 많은 주유소가있는 경우에도 모든 경로 최단 경로에 [Johnson 's Algorithm] (http://en.wikipedia.org/wiki/Johnson%27s_algorithm)을 사용하는 것이 좋습니다. – Nuclearman
당신은 모든 주유소들 사이의 거리를 찾을 필요가 없습니다. 내 대답을보십시오 ... –
@PavelGatnar : 모든 주유소 사이의 거리를 찾는 것은 ** O (V^2 * G) **입니다. 일단 내가 이것을 고려하면, 내 대답은 여전히 당신과 똑같은 복잡성을 가지고 있습니다 (실제로는 약간 더 빠름). 잘 했어! –
주유소 정점 사이의 거리는 지정된 범위 내의 미해결 주유소 꼭지점을 모두 검색하는 Dijkstra 알고리즘의 또 다른 수정에 따라 필요에 따라 계산되는 Dijkstra 알고리즘의 수정 사항이 있습니다.
익스트라 메인 루프에서 다음 단계를 수행한다.
1. 주 우선 순위 대기열에서 주유소를 가져옵니다.
2. 완료되면 종료하십시오.
3. 실제 주행 거리와 함께 미해결 인접 주유소를 제공하기 위해 Sub-Dijkstra를 호출하십시오.
서브 익스트라는 자신의 우선 순위 큐를 이용하여 연료의 범위 내의 모든 버텍스에 대한 실제 주유소에서 최단 경로를 탐색 (큐가 빌 때까지) 및 핸들 상태에 기초하여 주유소 도달 :
* 이미 메인 해결 - 나가는 가장자리를 처리하지 마십시오.
*하는 주요 대기열에서 대기 - 업데이트 거리 (낮은 decreaseKey 다음) 및 경로
을 * 다른 주요 큐
데이터 범위가 무엇에 넣어? –
얼마 전에 질문을 보았 기 때문에 범위를 정확히 기억하지 못합니다. O (mn logn)에 대한 느낌은 내가 처음 질문을 보았을 때였습니다. 다른 시간 복잡성을 가진 솔루션을 제안하십시오. 나는 아무 것도 갖고 있지 않다. :) – therealone
전기 자동차를위한 실제 매우 ;-) –