07. 그림 6 관광 계획 [Dijkstra 알고리즘]

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

#include
#define maxsize 501
#define inf 100000
using namespace std;
int n, m, s, d;
int dist[maxsize];
int cost[maxsize];
int value[maxsize][maxsize];
int G[maxsize][maxsize];
bool collected[maxsize];

void build()
{
	int v1, v2, d1, c1;
	cin >> n >> m >> s >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			G[i][j] = inf;
			value[i][j] = inf;
		}
		cost[i] = 0;
		dist[i] = inf;
		collected[i] = false;
	}
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2 >> d1 >> c1;
		G[v1][v2] = d1;
		G[v2][v1] = d1;
		value[v1][v2] = c1;
		value[v2][v1] = c1;
	}
}

void init()
{
	dist[s] = 0;
	collected[s] = true;
	for (int i = 0; i < n; i++) {
		if (G[s][i]) {
			dist[i] = G[s][i];
			cost[i] = value[s][i];
		}
	}
}

int findmin()
{
	int min = inf;
	int xb = -1;
	for(int i=0;i<n;i++)
		if (s != i && !collected[i] && dist[i] < min) {
			min = dist[i];
			xb = i;
		}
	return xb;
}

void Dijkstra()
{
	init();
	while (1) //      
	{
		int v = findmin();
		if (v == -1)
			break;
		collected[v] = true;
		for (int i = 0; i < n; i++) {
			if (!collected[i] && G[v][i])
				if (dist[v] + G[v][i] < dist[i]) {
					dist[i] = dist[v] + G[v][i];
					cost[i] = cost[v] + value[v][i];
				}
				else if (dist[v] + G[v][i] == dist[i] && cost[v] + value[v][i] < cost[i]) {
					cost[i] = cost[v] + value[v][i];
				}
		}
	}
}

int main()
{
	build();
	Dijkstra();
	cout << dist[d] << " " << cost[d];
	return 0;
}