[구름 IDE] 비타알고 시즌2 학교 지도 만들기(★3)

 

 

 

 

 

문제

소스코드

#include<iostream>
#include<queue>
 
constexpr int MAX_V = 20001;
constexpr int MAX_E = 100001;
constexpr int INF = INT32_MAX;
 
using namespace std;
 
struct Node {
    int        node;
    int        weight;
public:
    Node() = default;
    Node(int n,int w):node(n),weight(w) {}
    bool operator<(const Node& rhs)const {
        return weight > rhs.weight;
    }
 
};
 
 
void Dijkstra(int started,std::vector<vector<Node>>& vs, vector<int>& ws) {
    priority_queue<Node> queue;
    ws[started] = 0;
    queue.emplace(Node{ started,0 });
 
    while (queue.empty() == false) {
        
        int n = queue.top().node;
        int w = queue.top().weight;
        queue.pop();
 
        for (const auto& i : vs[n]) {
            int around_n = i.node;
            int around_w = i.weight+w;
            if (ws[around_n] > around_w) {
                ws[around_n] = around_w;
                queue.emplace(Node{ around_n,around_w });
            }
        }
    }
}
 
int main() {
    int V, E;
    int u, v, w;
    int x;
    std::cin >> V >> E;
 
    vector<vector<Node>>    nodes(V + 1);
    vector<int>                weight(V + 1, INF);
 
    for (int i = 0; i < E; ++i) {
        std::cin >> u >> v >> w;
        nodes[u].emplace_back(Node{ v,w });
        nodes[v].emplace_back(Node{ u,w });
 
    }
    std::cin >> x;
    Dijkstra(x, nodes, weight);
 
    for (int i = 1; i <= V; ++i) {
        if (weight[i] == INF)
            std::cout << -1 << "\n";
        else
            std::cout << weight[i] << "\n";
    }
}

후기

다익스트라 알고리즘을 풀었다. 

 

전에 백준에서 풀어봤던 다익스트라와 다르게 같은 노드에도 여러 간선이 있는 버전이었지만 크게 문제가 되지 않았다.

 

다익스트라를 써야 하는 문제인지 알 수 있는 하나의 방법은 "하나의 시작점으로부터 다른 모든 정점까지의 거리"라는 문장이 있는지 확인하는 것이다.

 

 

 

출처 및 레퍼런스

위클리 비타알고 시즌2 강의 링크:  https://edu.goorm.io/lecture/15551/%25ED%2594%2584%25EB%25A6%25AC%25EB%25AF%25B8%25EC%2597%2584-%25EC%2595%258C%25EA%25B3%25A0%25EB%25A6%25AC%25EC%25A6%2598-%25EC%259C%2584%25ED%2581%25B4%25EB%25A6%25AC-%25EB%25B9%2584%25ED%2583%2580%25EC%2595%258C%25EA%25B3%25A0-%25EC%258B%259C%25EC%25A6%258C2-%25EC%259E%2585%25EB%25AC%25B8%25ED%258E%25B8

 

 

* 해당 강의가 유료 전환됨으로 인해 '테스트 케이스', ' 해설 내용'은 공유하지 않고 게시하였습니다. 그래도 게시글에 문제가 있는 경우 알려주시면 수정하겠습니다.

 

관련 글

다익스트라 알고리즘(Dijkstra algorithm)

[백준] 1753번 최단경로