[백준 1916] 최소비용 구하기

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

1916번: 최소비용 구하기

 

다익스트라 연습 문제이다.

 

전부 c로 구현하면 좋겠지만 priority_queue는 귀찮아서 stl로 가져와서 써먹었다.

 

만약에 priority_queue를 구현한다면 알고리즘 시간에 배웠던 heap을 이용하여 조건을 더 추가하여

만들면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#define INF 1000000000

using namespace std;

int N, M;
int go[1001];

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

struct Node {
	struct Edge* head;
};

Node node[1001];
Edge dummy[100001], dummy_[1001];
int dummyCnt;

Edge* getEdge(int next_node, int distance) {
	Edge* ret = &dummy[dummyCnt++];
	ret->next_node = next_node;
	ret->distance = distance;
	ret->next = NULL;
	return ret;
}

void initialization(int node_cnt) {
	int i;
	for (i = 1; i <= node_cnt; i++) {
		node[i].head = &dummy_[i];
		go[i] = INF;
	}
}

void node_push(int cur, int next, int distance) {
	Edge* edge = getEdge(next, distance);
	edge->next = node[cur].head->next;
	node[cur].head->next = edge;
}

int dijkstra(int start, int end) {
	int distance, cur, next, next_dist;
	Edge* ptr;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	go[start] = 0;
	while (!pq.empty()) {
		distance = -pq.top().first;
		cur = pq.top().second;
		pq.pop();
		if (distance > go[cur]) continue;
		
		ptr = node[cur].head;
		while(ptr->next) {
			ptr = ptr->next;
			next = ptr->next_node;
			next_dist = go[cur] + ptr->distance;
			if (next_dist < go[next]) {
				go[next] = next_dist;
				pq.push({ -go[next], next });
			}
		}
	}

	return go[end];
}

int main(int argc, char* argv[]) 
{
	int i, x, y, distance, start, end;

	scanf("%d", &N);
	scanf("%d", &M);

	initialization(N);

	for (i = 0; i < M; i++) {
		scanf("%d %d %d", &x, &y, &distance);
		node_push(x, y, distance);
	}

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

	printf("%d\n", dijkstra(start, end));

	return 0;
}