[백준/c++] 1753번: 최단경로

 

 

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

1753번: 최단경로

 

문제 요약

 

방향 그래프, 시작점에서 다른 모든 정점으로의 최단 경로 구하기

서로 다른 두 정점 사이에 여러 개의 간선 존재할 수 있다.

 

입력 형태

 

정점의 개수 V(1 ≤ V ≤ 20,000) 간선의 개수 E(1 ≤ E ≤ 300,000)

시작 정점의 번호 K(1 ≤ K ≤ V)간선 u, v, w (u에서 v로 가는 가중치 w인 간선, w ≤ 10)

 

출력 형태

 

i번째 줄에 i번 정점으로의 최단 경로의 경로값 출력 (경로 존재하지 않다면 INF)

 

 

---

 

 

방향 그래프 + 시작점에서 다른 모든 정점으로의 최단 경로 → 다익스트라 알고리즘

 

#include <iostream>
#include <queue>
#include <vector>
#define NUM 20002
#define INF 0x7fffffff
using namespace std;
int V, E, K, dist[NUM];
vector<pair<int, int>> graph[NUM];

struct Info{
    int index;
    int dis;
    Info(){}
    Info(int index, int dis) : index(index), dis(dis) {}
    bool operator<(const Info& inf) const{
        return dis > inf.dis;
    }
};

void input(){
    cin >> V >> E;
    cin >> K;       //시작점 K
    for(int i=0; i<E; i++){
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from].push_back({to, weight});
    }
}

void solution(){
    priority_queue<Info> pq;
    for(int i=1; i<=V; i++) dist[i] = INF;
    pq.push({K, 0});
    dist[K] = 0;
    
    //연결된 정점 돌면서 갱신하기
    while(!pq.empty()){
        Info info = pq.top(); pq.pop();
        
        //갱신된(아닐수있음) 값과 시작점에서 현재 정점의 거리를 비교해서 동일하지 않으면 패스
        if(dist[info.index] != info.dis) continue;

        for(auto& i: graph[info.index]){ //info.index == info 정점의 인덱스, i = info의 연결된 정점
            auto [index, weight] = i;    //index == 연결 정점의 인덱스, weight == 연결 정점의 값(갱신될것)
            if(dist[index] <= dist[info.index] + weight) continue;
            dist[index] = dist[info.index] + weight; //정점의 거리 갱신
            pq.push({index, dist[index]});           //연결 정점 우선순위 큐에 추가
        }
    }
    
    for(int i=1; i<=V; i++){
        dist[i] == INF ? cout << "INF\n" : cout << dist[i] << '\n';
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!