[백준] 1753번 : 최단경로 (C++)

1753번 : 최단경로

---

문제)

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

 

 

입력 :

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

 

 

 

출력 :

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <queue>
 
#define INF 99999999
 
using namespace std;
 
int v, e;
int k;
vector<vector<pair<int, int>>> vec;
vector<int> dist;
// 우선순위 큐 사용
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
// 다익스트라 풀이
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> v >> e;
    vec.resize(v + 1, vector<pair<int, int>>());
    dist.resize(v + 1, INF);
 
    cin >> k;
    dist[k] = 0;
    pq.push(make_pair(0, k));
 
    int a, b, c;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
        vec[a].push_back(make_pair(b, c));
    }
 
    // 우선순위 큐를 이용하여 가지고 있는 자료 중
    // 가장 짧은 거리의 노드를 찾는다.
    while (!pq.empty())
    {
        int d = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
 
        // 보고 있는 노드가 가장 짧은 거리의 노드가 아니라면 continue;
        if (dist[cur] != d) continue;
 
        // 현재 노드에서 갈 수 있는 노드들의 최단 거리를 갱신해준다.
        for (int i = 0; i < vec[cur].size(); i++)
        {
            int nxt = vec[cur][i].first;
            int nd = dist[cur] + vec[cur][i].second;
 
            // 최단거리가 갱신이 가능하다면 갱신해주고 우선순위 큐에 넣어준다.
            if (dist[nxt] > nd)
            {
                dist[nxt] = nd;
                pq.push(make_pair(nd, nxt));
            }
        }
    }
 
    for (int i = 1; i < v + 1; i++)
    {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << "\n";
    }
 
    return 0;
}

---

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

1753번: 최단경로