백준 1753번

백준 1753번(최단경로)

문제는 한 시작점으로부터 모든 정점까지의 최단경로를 구하는 문제였다. 그냥 다익스트라 알고리즘을 사용하여 쉽게 해결할 수 있었다. 모든 정점을 최댓값으로 초기화한 뒤 시작점부터 시작하여 거리를 갱신해나가는 알고리즘이다.

1. 시작 정점 결정 -> 현재 정점
2. 시작 정점 제외 모든 정점까지의 거리를 매우 큰 수로 설정
3. 현재 정점으로부터 갈 수 있는 모든 정점 확인 -> 현재 저장된 거리보다 더 짧은 거리로 이동할 수 있다면 거리 갱신
4. 방문 안한 정점 중에 가장 가까운 거리에 있는 정점을 현재 정점으로 설정
5. 모든 정점을 방문할 때까지 3~4과정을 반복

위 과정 중에 4번을 우선순위 큐를 사용하여 해결하였다.

#include <bits/stdc++.h>

using namespace std;

// Dijkstra algorithm

struct EDGE {
	int to, w;
};

bool operator < (EDGE a, EDGE b) {
	return a.w > b.w;
}

vector<EDGE> graph[20005];

int main() {
	int v, e;
	scanf_s("%d %d", &v, &e);

	int start;
	scanf_s("%d", &start);

	for (int i = 0; i < e; i++) {
		int from, to, w;
		scanf_s("%d %d %d", &from, &to, &w);
		graph[from].push_back({to, w});
	}

	vector<int> ans(v + 1);
	vector<int> chk(v + 1);
	fill(ans.begin(), ans.end(), 1e9);

	priority_queue<EDGE> pq;
	pq.push({ start, 0 });
	ans[start] = 0;

	while (pq.size()) {
		auto f = pq.top();
		pq.pop();
		if (chk[f.to])
			continue;
		chk[f.to]++;
		for (auto next : graph[f.to]) {
			if (ans[next.to] > next.w + f.w) {
				ans[next.to] = next.w + f.w;
				pq.push({ next.to, next.w + f.w });
			}
		}
	}

	for (int i = 1; i < ans.size(); i++) {
		if (ans[i] == 1e9) {
			printf("INF\n");
		}
		else {
			printf("%d\n", ans[i]);
		}
	}

	return 0;
}