PAT 데이터 구조 06 - 그림 5. 관광 계획 (25) Dijkstra 최 단 경로 알고리즘

자가 운전 여행 노선 도 를 보면 도시 간 고속도로 길이 와 이 도로 에서 받 아야 할 통행 료 를 알 수 있 을 것 이다.지금 은 상담 하 러 온 관광객 들 이 출발지 와 목적지 사이 의 가장 짧 은 경 로 를 찾 을 수 있 도록 프로그램 을 써 야 한다.만약 몇 개의 경로 가 모두 가장 짧다 면, 가장 싼 경 로 를 출력 해 야 한다.
형식 설명 입력:
입력 설명: 데 이 터 를 입력 한 첫 번 째 줄 은 4 개의 정수 N, M, S, D 를 제시 합 니 다. 그 중에서 N (2 < = N < = 500) 은 도시 의 개수 이 고 도시 의 번호 가 0 이 라 고 가정 합 니 다 ~ (N - 1).M 은 고속도로 의 개수 이다.S 는 출발지 의 도시 번호 이다.D 는 목적지 의 도시 번호 다.그 다음 에 M 줄 에서 각 줄 은 고속도로 정 보 를 주 었 는데 그것 이 바로 도시 1, 도시 2, 고속도로 길이, 요금 액 이다. 중간 에 빈 칸 으로 나 누 면 숫자 는 모두 정수 이 고 500 을 초과 하지 않 는 다.보증 해 의 존 재 를 입력 하 십시오.
출력 형식 설명:
한 줄 에서 출력 경로 의 길이 와 비용 총액 은 숫자 간 에 빈 칸 으로 구분 되 며 출력 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
샘플 입 출력:
번호
입력
출력
1

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

3 40

2

2 1 0 1
1 0 2 3

2 3

처음으로 코드 로 이 Dijkstra 라 는 고전적 인 최 단 경로 알고리즘 을 실현 했다...
관건 은 모델 의 구축 에 있다. 데이터 구조 와 알고리즘 이 맞 으 면 코드 를 쓰 는 것 이 순리 적 인 일이 다.
모든 도시 의 결산 점 에 대해 우 리 는 그 번 호 를 기록 해 야 한다. 출발점 까지 의 총 거리 와 총 비용 은 처음에 이미 확 정 된 도 시 는 출발점 도시 만 있 고 나머지 도 시 는 모두 확정 되 지 않 은 도시 집합 에 있다.
매번 에 확정 되 지 않 은 도시 집합 에 대해 순 서 를 매기 고 가장 작은 (출발점 에서 가장 가 까 운 돈 을 절약 하 는 것) 을 꺼 내 처리 하 며 이 도 시 를 다른 미 확정 도시 의 선구자 로 하 는 것 이 더 좋 은 지 판단 한다. 만약 에 다른 미 확정 도시 에서 출발점 까지 의 총 거리 와 총 비용 을 업데이트 한다.
PS: 경 로 를 출력 하려 면 도시 데 이 터 를 업데이트 할 때 전구 도 시 를 기록 하 는 배열 을 추가 할 수 있 습 니 다.

/*2015.7.16cyq*/
//    ，Dijkstra  
#include 
#include 
#include 
#include 
using namespace std;

const int MAX=2147483647;
//ifstream fin("case1.txt");
//#define cin fin
struct road{
	int length;
	int money;
	road(int len,int mon):length(len),money(mon){}
};
struct city{
	int cityNum;	//    
	int totalLength;//       
	int totalMoney;	//       

	city(int num,int len,int mon):cityNum(num),totalLength(len),
		totalMoney(mon){}//    

	bool operator < (const city &a)const{//  >N>>M>>S>>D;
	vector > edges(N,vector(N,road(-1,-1)));//-1，     
	int a,b,c,d;
	while(M--){
		cin>>a>>b>>c>>d;
		edges[a][b].length=c;
		edges[b][a].length=c;
		edges[a][b].money=d;
		edges[b][a].money=d;
	}
	
	city cur(S,0,0);//    ，       0
	vector UD;//        
	for(int i=0;i pathPre(N,-1); //               ，        
	while(cur.cityNum!=D){
		for(auto it=UD.begin();it!=UD.end();it++){//         ，           ，            
			if(edges[cur.cityNum][(*it).cityNum].length>0){//  
				int tmpL=cur.totalLength+edges[cur.cityNum][(*it).cityNum].length;
				if(tmpL