5 Problem B : 최단경로

Problem B : 최단경로

 

제한시간: 1000 ms    메모리제한: 64 MB

 

 

그래프가 입력으로 들어왔을 때 1번 정점부터 N번 정점으로 이동할 경우의 최단 경로를 구하는 프로그램을 작성하라.

 

정점의 개수와 간선의 개수가 크기 때문에 보통의 알고리즘을 이용해서는 제시간에 답을 찾기 어렵기 때문에, 

효율적인 알고리즘을 고안하여 프로그램을 작성해 보자.

 

첫 번째 줄에는 그래프의 정점의 개수 N(N≤20,000)과 간선의 개수 M(M≤100,000)이 입력된다. 그 다음 줄부터 M개의 간선의 정보가 입력된다. 간선의 정보는 3개의 정수 a, b, c로 숫자마다 공백을 사이에 두고 입력되는데 정점 a에서 정점 b로 갈 때 c만큼의 비용이 든다는 것을 의미한다. a와 b는 1이상 N이하의 숫자이며, c의 경우 1만 이하의 양의 정수이며, 간선을 통해 a에서 b로만 이동이 가능하나, b에서 a로는 이동이 불가능한 단방향 간선이다.

 

 

1번 경로에서 N번 경로 까지 가는 최단 경로 값을 출력한다.

 

4 4

1 2 3

2 3 4

3 4 2

1 4 5

 

5

 

#include <stdio.h>

const int LN = 3e8;
struct data {
	int node, dis;
	data *next;
	data *myAlloc(int _node, int _dis, data *_next) {
		node = _node, dis = _dis, next = _next;
		return this;
	}
} *stack[20010], buf[100100]; // 정점, 버퍼 저장
int N, M, bn;
int D[20010], heap[100100], chk[20010], hn; // 누적, 최소힙, 확정, 힙길이

void Swap(int &x, int &y) { int z = x; x = y; y = z; }

void push(int p)
{
	if (p <= 1 || D[heap[p / 2]] <= D[heap[p]]) return; // 힙에 하나만 있고, 부모가 더 작으면 오케이, 최소힙트리
	Swap(heap[p / 2], heap[p]);
	push(p / 2);
}

void pop(int p)
{
	int np = (p << 1);
	if (np > hn) return;
	if (np < hn && D[heap[np]] > D[heap[np + 1]]) np++;
	if (D[heap[p]] <= D[heap[np]]) return;
	Swap(heap[p], heap[np]);
	pop(np);
}

void dijkstra()
{
	int i, j, k, node;
	for (i = 2; i <= N; i++) D[i] = LN;
	heap[++hn] = 1; // 힙트리 구성. 간선은 1이상
	while (1) {
		node = heap[1]; // 제일 위에 것
		heap[1] = heap[hn--]; // 제일 아랫것 올리기
		pop(1); // 꺼내기
		if (chk[node]) continue;
		chk[node] = 1; // 확실
		if (node == N) break; // 목표점 도달
		for (data *p = stack[node]; p != 0; p = p->next) { // 시작점에서 node 에 연결된 것 모두 돌아가면서 검사
			if (D[p->node] > D[node] + p->dis) { // 현재 누적값 + 간선거리가 더 작으면
				D[p->node] = D[node] + p->dis;
				heap[++hn] = p->node;
				push(hn);
			}
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	int a, b, c;
	scanf("%d %d", &N, &M);
	while (M--) { // 간선의 갯수만큼
		scanf("%d %d %d", &a, &b, &c);
		stack[a] = buf[bn++].myAlloc(b, c, stack[a]);
	}
	dijkstra();
	printf("%d\n", D[N]);
	return 0;
}