07 - 그림 6 관광 계획 (Dijkstra 알고리즘 (단원 최 단 경로 알고리즘))

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

출력 예시:

3 40

코드

#include
using namespace std;
#define Maxn 1000

int a[550][550];
int s[550][550];
int d[550];
int f[550];
int visited[550]={0};
int v,b,n,m;
void Dijkstra(int x){
	for(int i=0;i<v;i++){	// 0 i                 
		d[i]=a[x][i];
		f[i]=s[x][i];
	}
	visited[x]=1;	//      
	d[x]=0,f[x]=0;	 

	for(int i=1;i<v;i++){
		int tail,j,mm=Maxn;
		for(j=0;j<v;j++){	//         
			if(!visited[j]&&d[j]<mm){
				mm=d[j];
				tail=j;
			}
		}
		visited[tail]=1;
		
		for(j=0;j<v;j++){
			if(!visited[j]){
				if(d[tail]+a[tail][j]<d[j]){	//     
					d[j]=d[tail]+a[tail][j];
					f[j]=f[tail]+s[tail][j];
				}else if(d[tail]+a[tail][j]==d[j]	//     
				&&f[tail]+s[tail][j]<f[j]){
					f[j]=f[tail]+s[tail][j];
				} 
			}
		}
	}
}
int main(){
	cin>>v>>b>>n>>m;
	for (int i = 0; i < v; i++)	//              
    for (int j = 0; j < v; j++) {
        a[i][j] = Maxn;
        s[i][j] = Maxn;
    }
	int q,w,e,r;
	for(int i=1;i<=b;i++){	//     
		cin>>q>>w>>e>>r;
		a[q][w]=a[w][q]=e;
		s[q][w]=s[w][q]=r;
	}
	Dijkstra(n);	//Dijkstra   
	cout<<d[m]<<" "<<f[m];
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

PAT 1012Invert a Binary Tree 반전 두 갈래 트리(반전 트리, 레이어 순서, 중간 순서)

전송 제목은 두 갈래 트리를 지정합니다. 반전 후 두 갈래 트리의 층차 역행 서열과 중차 역행 서열을 출력해야 합니다. 반전 조작에 관해서는 후순이나 선순이 모두 가능하다...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

07 - 그림 6 관광 계획 (Dijkstra 알고리즘 (단원 최 단 경로 알고리즘))

좋은 웹페이지 즐겨찾기