백준 1753번: 최단경로 (C++)

 

문제 링크 : www.acmicpc.net/problem/1753

 

 

단순한 다익스트라 알고리즘 문제다. 

 

 

<전체적인 알고리즘>

내 블로그에 다익스트라 알고리즘에 대해 다 설명해 놓았다.  

다익스트라 알고리즘 : wlshddlek.tistory.com/36?category=887632 

 

 

 

 

<전체 코드>

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

vector<pair<int, int>> a[20002];
int d[20002];
int INF = 987654321;

void dijkstra(int start)
{
	fill(&d[0], &d[20001], INF);
	
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0,start));
	d[start] = 0;

	while (!q.empty())
	{
		int node = q.top().second;
		int distance = -q.top().first;
		q.pop();

		if (d[node] < distance)continue;

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i].first;
			int nextdistance = a[node][i].second + distance;
			if (nextdistance < d[next])
			{
				d[next] = nextdistance;
				q.push(make_pair(-nextdistance, next));
			}
		}
	}
}

int main()
{
	int v, e,k;
	cin >> v >> e>>k;

	for (int i = 0; i < e; i++)
	{
		int n1, n2, w;
		cin >> n1 >> n2 >> w;
		a[n1].push_back(make_pair(n2, w));
	}

	dijkstra(k);

	for (int i = 1; i <= v; i++)
	{
		if (d[i] == INF)cout << "INF\n";
		else cout << d[i] << "\n";
	}

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.