80. 다익스트라 알고리즘

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

풀이 

- 다익스트라 알고리즘

- 거리 배열을 사용

- 현재지점까지의 거리 + 새로운 지점까지의 거리 vs 새로운 지점의 거리배열에 있는 거리 

=> 거리배열에 더 작은 값이 있다면 continue 

=> 아니라면 새로운거리로 배열의 값을 업데이트 하고 큐에 푸시한다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

//80. 다익스트라 알고리즘
struct Edge{
    int vex; //정점
    int dis; //거리
    Edge(int a, int b){
        vex=a;
        dis=b;
    }
    bool operator<(const Edge &b) const{
        return dis>b.dis;
    }
};

int main(){
    vector<pair<int, int> > graph[30];
    priority_queue<Edge> Q;
    int i, n, m, a, b, c;
    scanf("%d %d", &n, &m);
    vector<int> dist(n+1, 2147000000); //거리를 담을 벡터배열
    for(i=1;i<=m;i++){
        scanf("%d %d %d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
    Q.push(Edge(1,0));
    dist[1]=0;
    while(!Q.empty()){
        int now=Q.top().vex;
        int cost=Q.top().dis;
        Q.pop();
        if(cost>dist[now]) continue;
        for(i=0;i<graph[now].size();i++){
            int next=graph[now][i].first;
            int nextDis=cost+graph[now][i].second;
            if(dist[next]>nextDis){
                dist[next]=nextDis;
                Q.push(Edge(next, nextDis));
            }
        }
    }
    for(i=2;i<=n;i++){
        if(dist[i]!=2147000000) printf("%d : %d\n", i, dist[i]);
        else printf("%d : impossible\n", i);
    }
    
    return 0;
}