BOJ_1753 / C++

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

1753번: 최단경로

백준 온라인저지 1753번 문제입니다. 

다익스트라

#include<iostream>
#include<vector>
#include<queue>
#define MAX 20001
#define INF 987654321
#define endl "\n"
using namespace std;

int node[MAX];
vector<pair<int, int>> connect[MAX];
int V, E, K;

void init(int a)
{
	for (int i = 1; i <= a; i++)
	{
		node[i] = INF;
	}
}
void Input() {
	int u, v,w;
	cin >> V >> E >> K;
	init(V);
	while (E--)
	{
		cin >> u >> v >> w;
		connect[u].push_back(make_pair(v, w));
	}
}

void dijkstra(int a)
{
	node[a] = 0;
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, a));
	while (!q.empty())
	{
		int dist = -1*q.top().first;
		int current = q.top().second;
		q.pop();

		if (node[current] < dist) continue;

		for (int i = 0; i < connect[current].size(); i++)
		{
			int next = connect[current][i].first;
			int next_dist = dist + connect[current][i].second;

			if (next_dist < node[next])
			{
				node[next] = next_dist;
				q.push(make_pair(-1 * next_dist, next ));
			}
		}
	}
}

int main(void) {
	Input();
	dijkstra(K);
	for (int i = 1; i <= V; i++)
	{
		if (node[i] == INF)
		{
			cout << "INF" << endl;
		}
		else
		{
			cout << node[i] << endl;
		}
	}
}

방향 그래프를 제시받아서 시작점으로 부터 모든 정점까지의 거리를 출력하는 문제입니다.

다익스트라 알고리즘으로 출발점으로 부터 모든 간선까지의 거리 그래프를 만들고 차례대로 출력했습니다.

우선 큐에 다음 조사 노드를 넣을때 -부호를 붙이는 이유는 priority_queue의 defult는 내림차순인 것을 이용해서 가중치가 거리가 작은 노드순으로 정렬 목적입니다.

 

문제해결중 만난 어려움

다음 노드에 대한 조사를 하기위해 우선 큐에 넣게 되는데 (다음 노드, 가중치) 순서로 큐에 넣어서 시간초과를 받았고,

(가중치, 다음노드) 순으로 큐에 넣어 가까운 거리순 조사할 수 있도록 수정해서 정답처리 받았습니다.