백준 1753 최단경로 c++ [컴공과고씨]

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

1753번: 최단경로

 

문제 간단 정리

정점이 주어질 때 시작점이 주어지고 그 시작점으로 부터 각 정점의 최단거리를 출력하는 문제.

 

문제 해결 방법

다익스트라 알고리즘을 사용하여 쉽게 풀 수 있는 문제이다.

다익스트라를 모른다면 https://hagisilecoding.tistory.com/134 여기서 보고 오시면 쉽게 풀 수 있습니다.

 

전체 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
int INF = 98765432; 
int dp[20003];
vector<pair<int, int>> v[20003];
void fc(int st){ // 다익스트라 
    memset(dp, INF, sizeof(dp)); // 초기값 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 우선순위 큐
    pq.push({0, st});
    dp[st] = 0; // 시작정점 거리 0
    while(!pq.empty()){
        int x = pq.top().second; // 현재 정점
        int cost = pq.top().first; // 현재 정점까지 거리
        pq.pop();
        for (int i = 0; i < v[x].size();i++){
            int nx = v[x][i].first; // 다음 정점
            int ncost = cost + v[x][i].second; // 다음정점까지 거리
 
            if(dp[nx] > ncost){ // 다음 정점에 기록된 거리와 비교
                pq.push({ncost, nx}); 
                dp[nx] = ncost;
            }
        }
    }
}
int main(){
    int V, E, K;
    cin >> V >> E >> K;
    int a1, a2, a3;
    for (int i = 0; i < E;i++){
        cin >> a1 >> a2 >> a3;
        v[a1].push_back({a2, a3});
    }
    fc(K);
    for (int i = 1; i <= V;i++){
        if(dp[i] < INF)
            cout << dp[i] << '\n';
        else
            cout << "INF" << '\n';
    }
    return 0;
}