백준 1753 c++

다익스트라알고리즘을 이용해 처음 플어본 문제다.
메모리초과와 시간초과를 해결하는 과정이 어려웠다.
시간초과를 해결한 방법은 다익스트라 알고리즘에서 우선순위큐를 사용하는데
구분하기 편하게 노드값은 전부 왼쪽, 거리값은 전부 오른쪽에 저장하게 했다. 그러나 우선순위 큐에서 조건을 명시하지 않으면 왼쪽을 기준으로 정렬하기에 노드값 기준으로 정렬하게 되면 시간초과가 발생한다.
큐 저장 식을 바꾸고 나서 시간초과를 해결했다.
다익스트라 연습을 위한 문제풀이가 더 필요하다고 생각한다.

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

#define INF 2100000000

using namespace std;

int V, E, K;
vector <vector<pair<int, int>>> graph;
vector <int> dist;

void input_graph()
{
	int i;
	int u, v, w;

	cin >> V >> E;//노드개수 V, 간선개수 E 입력받기
	cin >> K;// 시작점 K입력받기
	graph.resize(V + 1);
	dist.resize(V + 1, INF);//시작점에서부터 모든 노드까지의 값을 담을 벡터 초기화
	for (i = 0; i < E; i++)
	{
		cin >> u >> v >> w;//시작노드, 도착노드, 가중치 입력받기
		graph[u].push_back({ w, v });//방향그래프/ {도착노드, 가중치}
	}

	return;
}

void dijkstra()
{
	priority_queue<pair<int, int>> pq;// 왼쪽에 가중치를 두어야 하는 이유
	// 조건이 없다면 왼쪽을 기준으로 정렬을 하기 때문에 순서 맞춘다고 왼쪽에 도착점, 오른쪽에 가중치를 두면, 도착점기준으로 정렬이 되기 때문에 시간초과가 난다!!!!!
	//조건이 없으므로 first값 기준 내림차순으로 정렬
	int current_node, current_dist, next_node, next_dist;
	int i;
	
	dist[K] = 0;
	pq.push({ 0, K });
	while (!pq.empty())
	{
		current_node = pq.top().second;//방문하고 있는 노드 번호
		current_dist = -pq.top().first;//방문하고 있는 정점의 거리
		pq.pop();
		if (dist[current_node] < current_dist)
		{
			continue;
		}
		for (i = 0; i < graph[current_node].size(); i++)
		{
			next_node = graph[current_node][i].second;//인접 노드 번호
			next_dist = current_dist + graph[current_node][i].first;//인접노드까지 거리
			if (next_dist < dist[next_node])//새로 구한 거리값이 기존노드까지의 거리값보다 작다면
			{
				dist[next_node] = next_dist;//거리값 더 작은걸로 바꾸고
				pq.push({ -next_dist, next_node });//큐에 추가
			}
		}
	}

	return;
}

void find_answer()
{
	int i;

	dijkstra();
	for (i = 1; i < V+1; i++)
	{
		if (dist[i] == INF)
		{
			cout << "INF\n";
		}
		else
		{
			cout << dist[i] << "\n";
		}
	}

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input_graph();
	find_answer();

	return 0;
}
//ㅗㅗ