[백준] C++ 최단 경로 구하기(1753)

이 문제는 시작점에서 다른 정점까지의 최단 경로값을 구하는 문제이다. 다익스트라 알고리즘을 사용한다.

이 문제에서 주의 깊게 보아야 하는 점은 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다는 것이다.

이미 최적의 값으로 갱신된 노드는 다시 방문하지 않게 만들어줘야 한다.(시간초과 방지)

if (dist[cur] < cost) continue; 만약 최적값으로 갱신이 되었다면??

이렇게 해도 되고 아니면 visited배열을 이용해서 방문된 노드를 저장해 주면 된다. 이미 방문한 노드는 다시 방문하지 않는다!

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321;
using namespace std;
vector<pair<int,int>>v[1001];
priority_queue<pair<int, int>>pq;
int arr[1001];
int main(void)
{
	int N, M = 0;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c=0;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
	}
	int start, end = 0;
	cin >> start >> end;

	pq.push({ 0,start });

	for (int i = 1; i <= N; i++)
	{
		arr[i] = INF;
	}
	arr[start] = 0;
	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (distance > arr[cur])//이미 최적의 값으로 갱신이 되었다면?
		{
			continue;
		}
		for (int i = 0; i < v[cur].size(); i++)
		{
			int next = v[cur][i].first;
			int nextdistance = distance+v[cur][i].second;

			if (nextdistance < arr[next])
			{
				arr[next] = nextdistance;
				pq.push({ -nextdistance,next });
			}
		}
	}

	cout << arr[end];
}

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321;
using namespace std;
vector<pair<int,int>>v[1001];
priority_queue<pair<int, int>>pq;
int arr[1001];
int visited[1001];
int main(void)
{
	int N, M = 0;
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c=0;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
	}
	int start, end = 0;
	cin >> start >> end;

	pq.push({ 0,start });

	for (int i = 1; i <= N; i++)
	{
		arr[i] = INF;
	}
	arr[start] = 0;
	while (!pq.empty())
	{
		int distance = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (visited[cur] == 1)
		{
			continue;
		}
		visited[cur] = 1;
		
		for (int i = 0; i < v[cur].size(); i++)
		{
			int next = v[cur][i].first;
			int nextdistance = distance+v[cur][i].second;

			if (nextdistance < arr[next])
			{
				arr[next] = nextdistance;
				pq.push({ -nextdistance,next });
			}
		}
	}

	cout << arr[end];
}