[백준] 1753번 : 최단경로 (C++, 다익스트라)

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

1753번: 최단경로

우선순위 큐에 { 노드번호, 가중치 } 순서로 넣으면 정렬이 노드 번호가 작은 순서, 같으면 가중치가 작은 순서로 우선순위 큐가 작동하기 때문에 시간초과가 떴다.

따라서, { 가중치, 노드번호 } 순으로 넣어 해결하였다. 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int V, E,K;
vector<pair<int, int>> vec[20001];
int Dist[20001];
int INF = 987654321;

void Solution(int Start)
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;

    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();

        for (int i = 0; i < vec[Cur].size(); i++)
        {
            int Next = vec[Cur][i].first;
            int nCost = vec[Cur][i].second;

            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}

int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> V >> E >> K;

	for (int i = 1; i <= V; i++) {
		Dist[i] = INF;
	}
	int u, v, w;
	for (int i = 0; i < E; i++){
		cin >> u >> v >> w;
		vec[u].push_back({ v,w });
	}

	Solution(K);
	for (int i = 1; i <=V ; i++){
		if (Dist[i] == INF) cout << "INF" << endl;
		else cout <<Dist[i] << endl;
	}

}