[백준 11779] 최소비용 구하기 2

문제 링크 => 11779번: 최소비용 구하기 2 (acmicpc.net)

11779번: 최소비용 구하기 2

 

전형적인 다익스트라 문제이다.

 

다익스트라 알고리즘을 활용하여 최소거리를 구할 수 있어야 하며 동시에 경로까지 출력해야 하는 문제이다.

경로를 추적하기 위한 배열 trace 를 이용하였다.

시작 지점으로부터 다음 지점(next)까지의 최소 거리를 Distance[next] 라고 할 때 해당 값이 update 될 때마다

현재 위치(cur)에 대해서 trace[next] = cur 을 함으로써 추적해간다.

최적의 경로를 발견했다면 아래와 같은 방법으로 정점들을 구할 수 있다.

 

trace[next] = cur 와 같은 구조로 이뤄지며 end(E)에서 start(S)까지 다음과 같이 재귀적으로 구할 수 있다.

(1) trace[E]   = x1    : 정점 갯수는 2개다.

(2) trace[x1] = x2    : 정점 갯수는 3개다.

(3) trace[x2] = x3    : 정점 갯수는 4개다.

...

(n) trace[xn-1] = S : 정점 갯수는 n+1개이고 시작지점(S)에 도달하였다.

      따라서 정점들을 출력해가면서 함수를 역으로 리턴해가면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

struct Info {
	int x;
	int distance;
};

struct Edge {
	int next_node;
	int distance;
	Edge* next;
};

struct Node {
	struct Edge* head;
};

Node node[1001];
Info heap[100001];
int trace[1001], Distance[1001];
int n, m, heap_size;

#define INF 1000000000

Edge* make_edge(int next_node, int distance) {
	Edge* e = (Edge*)malloc(sizeof(Edge));
	e->next_node = next_node;
	e->distance = distance;
	e->next = nullptr;
	return e;
}

void init() {
	struct Edge* tmp;
	for (int i = 1; i <= n; i++) {
		tmp = (Edge*)malloc(sizeof(Edge));
		tmp->next = nullptr;
		node[i].head = tmp;
	}
}

void PQ_insert(Info tmp) {
	int x;
	x = ++heap_size;
	while ((x != 1) && (heap[x / 2].distance > tmp.distance)) {
		heap[x] = heap[x / 2];
		x /= 2;
	}
	heap[x] = tmp;
}

Info PQ_delete() {
	int parent, child;
	Info temp, ret;

	parent = 1, child = 2;
	ret = heap[1], temp = heap[heap_size--];
	while (child <= heap_size) {
		if ((child < heap_size) && (heap[child].distance > heap[child + 1].distance)) child++;
		if (temp.distance <= heap[child].distance) break;
		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}

	heap[parent] = temp;
	return ret;
}

void connect_edge(Edge* head, Edge* edge) {
	if (head->next == nullptr) {
		head->next = edge;
	}
	else {
		edge->next = head->next;
		head->next = edge;
	}
}

void show_answer(int trace[], int S, int x, int cnt) {
	if (x == S) {
		printf("%d\n", cnt);
		printf("%d ", x);
		return;
	}
	show_answer(trace, S, trace[x], cnt + 1);
	printf("%d ", x);
}

void Dijkstra(int S, int E) {
	Info tmp;
	int cur, distance, next, next_distance;
	for (int i = 1; i <= n; i++)
		Distance[i] = INF;
	
	tmp.x = S, tmp.distance = 0;
	PQ_insert(tmp);
	while (heap_size) {
		tmp = PQ_delete();
		cur = tmp.x, distance = tmp.distance;
		struct Edge* e = node[cur].head;
		while (e->next) {
			e = e->next;
			next = e->next_node, next_distance = distance + e->distance;
			if (next_distance < Distance[next]) {
				Distance[next] = next_distance;
				trace[next] = cur;
				tmp.x = next, tmp.distance = next_distance;
				PQ_insert(tmp);
			}
		}
	}

	printf("%d\n", Distance[E]);
	show_answer(trace, S, E, 1);
}

int main()
{
	int i, from, to, dist, start, end;
	struct Edge* edge;
	scanf("%d", &n); // 도시의 갯수
	scanf("%d", &m); // 버스의 갯수

	init();

	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &from, &to, &dist);
		edge = make_edge(to, dist);
		connect_edge(node[from].head, edge);
	}

	scanf("%d %d", &start, &end);
	Dijkstra(start, end);

	return 0;
}