최단 경로 - 우선 대기열 최적화 버전 (사실 조밀도는 최적화되지 않음)

Input
입력은 여러 그룹을 포함하고 각 그룹은 먼저 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 #include #include using namespace std; #define INF 1000000000 #define MAXN 1100 struct way { int s; int d;//distance bool operator <(const way k)const { return k.dQ; bool flag[MAXN]={false};//flag[i]==1 means it is in the end point set way temp,now; now.s=endpoint; now.d=0; Q.push(now); point[endpoint][endpoint]=0; while (!Q.empty ()) {now=Q.top ();Q.pop ();/use priority queue to ensure pop the point with minimal distance every time if(flag[now.s])continue;flag[now.s]=1;for(int i=1;i<=n;i++)//종점에서 뒤로 밀기 {if(!flag[i]&map[now.s][i]! [endpoint]+map[i][now.s]) {temp.s=i;temp.d=point[now.s][endpoint]+map[i][now.s];point[i][endpoint]=temp.d;Q.push(temp); } } } } void init()//초기화 {int i, j;int a, b, c;for(i=1;i오늘 한 마리의 소while2와 우선 대기열 최적화 문제를 이야기했는데 결론은 다음과 같다.
상기 코드 복잡도(v+e)log(e), 우선 대기열에 불필요한 변이 존재하기 때문에 최소 저장 거리를 사용할 수 있습니다. 복잡도가 vloge로 내려가도.반면 Dijkstra의 복잡도(비최적화판)는 O(n^2)이다.즉, 이 그림이 e=v^2까지 조밀하더라도 최소 최적화된 우선 대기열은 간단한 Dijkstra를 벗어나지 못한다는 것이다.
따라서 상기 코드는 최적화 작용을 하지 않습니다!그냥 쓰기 편할 뿐이야.
while2의 최적화 버전을 참고하십시오.
http://while2.blogcn.com/