최단 경로 - 우선 대기열 최적화 버전 (사실 조밀도는 최적화되지 않음)
입력은 여러 그룹을 포함하고 각 그룹은 먼저 n(n<=100)을 포함한다. 이 그룹의 데이터에 n개의 점이 있다는 것을 대표한다. 그 다음에 n*n의 행렬은 두 개의 거리(s에서 t의 거리는 t에서 s의 거리와 다를 수 있음)를 대표한다. 한 점에서 자신의 거리는 0이고 그 어떤 수는 1000보다 크지 않고 음정수가 아니다.숫자 주소는 1부터 n까지 표시됩니다.진 후에 부정수 그룹 s가 있고 t는 시작점 주소와 종점 주소를 대표하며 0 0으로 n=0으로 끝날 때 이 그룹의 데이터는 출력이 필요하지 않습니다.
Output
매 쌍의 s, t는 정수 출력에 대응하여 s에서 t까지의 최단 거리를 나타낸다.각 그룹의 데이터 뒤에 빈 줄 구분을 추가합니다.
Sample Input
5
0 3 6 8 9
5 0 6 9 4
1 3 0 84 1
45 1 2 0 4
1 4 5 8 0
1 2
1 3
1 4
5 4
4 3
4 1
3 4
0 0
2
0 1
1 0
1 2
1 1
0 0
0
Sample Output
3
6
8
8
2
3
9
1
0
//한 시간 동안 썼는데... struct가 번호보다 작은 재부팅에 대해 잘 알지 못했습니다./minimal path use priorityqueue #include
상기 코드 복잡도(v+e)log(e), 우선 대기열에 불필요한 변이 존재하기 때문에 최소 저장 거리를 사용할 수 있습니다. 복잡도가 vloge로 내려가도.반면 Dijkstra의 복잡도(비최적화판)는 O(n^2)이다.즉, 이 그림이 e=v^2까지 조밀하더라도 최소 최적화된 우선 대기열은 간단한 Dijkstra를 벗어나지 못한다는 것이다.
따라서 상기 코드는 최적화 작용을 하지 않습니다!그냥 쓰기 편할 뿐이야.
while2의 최적화 버전을 참고하십시오.
http://while2.blogcn.com/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
깨끗한 것을 보고 싶기 때문에 최적화 함수의 벤치마크에 이용되는 함수의 가시화를 해 보았다결정되지 않음 (자기 만족) 「헤이 이런 거 있어」라고 생각하는 사람 최적화 함수란? 거친 이미지로 1) x + 10 = 25 2) x + 60 = 15 3) x + 45 = 60 의 x를 기계에 구할 때 정확하게 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
