[백준 1753번] 최단경로

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

1753번: 최단경로

풀이) 

다익스트라알고리즘 개념을 이용하여 시작 노드를 기준으로 나머지 노드까지의 거리를 MAX로 설정해두고, queue에 담아둔 정보를 꺼내면서 거리가 더 작으면 나머지 노드까지의 거리들을 갱신하면 된다. 

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

int V, E, K, u, w, v, INF = 987654321;
vector<pair<int, int>> a[20001];

vector<int> Dijkstra(int vertex, int start)
{
    vector<int> d(vertex, INF);
    d[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty())
    {
        int distance = -pq.top().first;
        int current = pq.top().second;
        pq.pop();
        if (d[current] < distance)
            continue;
        for (int i = 0; i < a[current].size(); i++)
        {
            int next = a[current][i].first;
            if (d[next] > a[current][i].second + distance)
            {
                d[next] = a[current][i].second + distance;
                pq.push(make_pair(-(a[current][i].second + distance), next));
            }
        }
    }
    return (d);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> V >> E >> K;
    for (int i = 0; i < E; i++) {
        cin >> u >> v >> w;
        a[u].push_back(make_pair(v,w));
    }
    
    vector<int> dist = Dijkstra(V+1, K);
    
    for (int i = 1; i <= V; ++i) {
        if (dist[i] == INF)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!