BOJ (C/C++) 1753번: 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

---

풀이

다익스트라 알고리즘 사용, 현재 노드와 가까운 노드들을 탐색하며 가중치가 적은 간선부터 큐에 저장해서 최단 경로 구함.

---

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>
using namespace std;

vector<pair<int, int>> R[20001];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
int W[20001];

void Dijkstra(int s) {
	int now, next, weight;
	Q.push({ 0,s });
	W[s] = 0;
	while (!Q.empty()) {
		now = Q.top().second, weight = Q.top().first;
		Q.pop();

		// 현재 최단 거리일 땐 계산 x
		// if (W[now] < weight) continue;

		for (int i = 0; i < R[now].size(); i++) {
			next = R[now][i].first, weight = R[now][i].second;

			if (W[next] > W[now] + weight) {
				W[next] = W[now] + weight;
				Q.push({ W[next], next });
			}
		}
	}
}

int main() {
	int V, E, start;
	int u, v, w;

	scanf("%d %d", &V, &E);
	scanf("%d", &start);
	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &u, &v, &w);
		R[u].push_back({ v,w });
	}

	fill(W + 1, W + V + 1, INT_MAX);
	Dijkstra(start);

	//print
	for (int i = 1; i <= V; i++) {
		if (W[i] == INT_MAX) printf("INF\n");
		else printf("%d\n", W[i]);
	}

	return 0;
}

---

코드 2 (방문 처리 해줌)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>
using namespace std;

vector<pair<int, int>> R[20001];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
int W[20001];
bool visited[20001];

void Dijkstra(int s) {
	int now, next, weight;

	// starting point init
	Q.push({ 0,s });
	W[s] = 0;
	visited[s] = true;


	while (!Q.empty()) {
		weight = Q.top().first, now = Q.top().second;
		Q.pop();
		visited[now] = true;

		for (int i = 0; i < R[now].size(); i++) {

			next = R[now][i].first, weight = R[now][i].second;
			if (visited[next]) continue;

			if (W[next] > W[now] + weight) {
				W[next] = W[now] + weight;
				Q.push({ W[next], next });	
			}
		}
	}
}

int main() {
	int V, E, start;
	int u, v, w;

	// input
	scanf("%d %d", &V, &E);
	scanf("%d", &start);

	for (int i = 0; i < E; i++) {
		scanf("%d %d %d", &u, &v, &w);
		R[u].push_back({ v,w });
	}

	fill(W, W + V + 1, INT_MAX);
	Dijkstra(start);

	//print
	for (int i = 1; i <= V; i++) {
		if (W[i] == INT_MAX) printf("INF\n");
		else printf("%d\n", W[i]);
	}

	return 0;
}