[Cpp] 백준 1753번 최단 경로

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

1753번: 최단경로

 

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

using namespace std;

#pragma region 최단 경로
// 1. 정점의 개수 V, 간선의 개수 E 입력받는다.
// 2. 시작 정점의 번호 K를 입력받는다.
// 3. u v w를 입력받아서 그래프에 간선을 추가한다. u는 시작 정점, v는 도착 정점, w는 가중치
// 4. dist 배열을 -1로 초기화한다.
// 5. 다익스트라를 돌리면서 시작점 기준으로 모든 정점까지의 거리를 구한다.
// 6. 최단 거리이기 때문에 더 작은 값이 나오면 갱신한다.
// 7. dist 배열을 출력한다.

const int VMAX = 20001;

void dijkstra(int startVertex)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[startVertex] = 0;
    pq.push(make_pair(dist[startVertex], startVertex));

    while(!pq.empty())
    {
        int current = pq.top().second;
        int distance = pq.top().first;
        pq.pop();

        for(size_t i = 0; i < info[current].size(); i++)
        {
            int dest = info[current][i].first;
            int cost = info[current][i].second;

            if(dist[dest] == -1 || dist[dest] > distance + cost)
            {
                dist[dest] = dist[current] + cost;
                pq.push(make_pair(dist[dest], dest));
            }
        }
    }
    
}

void testMain()
{
    int V, E, K;
    cin >> V >> E;
    cin >> K;
    for(int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        info[u].push_back(make_pair(v, w));
    }

    for(int i = 1; i <= V; i++)
    {
        dist[i] = -1;
    }

    dijkstra(K);

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

#pragma endregion

//우선순위 큐 가중치를 어디에 둘것이냐
//큐 greater
//endl은 줄 바꿈과 동시에 출력버퍼를 비운다 이 과정에서 시간이 소모가 많이 됨.

 

핵심은 priority_queue 에 가중치를 무엇으로 둘거냐에 따라서 실행속도에 따른 풀이 통과의 당락이 결정됩니다.

시간 초과 때문에 생고생을 했습니다...