Beakjoon] 줄 세우기(백준 1753 코테) - 그래프 (C++) (다익스트라)

---

🅰️문제주소 : https://www.acmicpc.net/problem/1753

 

🚩문제 

 

 

🪡풀이 

 - 다익스트라 알고리즘을 사용한다 

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int V = 0;
    int E = 0;
    int start = 0;
    std::cin >> V >> E;
    std::cin >> start;
    
    typedef std::pair<int, int> edge;
    std::vector<int> visited;
    std::vector<int> min_distance;
    std::vector<std::vector<edge>> map;
    std::priority_queue<edge, std::vector<edge>, std::greater<edge>> q;

    visited.resize(V+1);
    min_distance.resize(V+1);
    map.resize(V+1);
    fill(min_distance.begin(), min_distance.end(), INT_MAX-1);
    fill(visited.begin(), visited.end(), 0);

    for (int i = 0; i < E; ++i)
    {
        int u, v, w;
        std::cin >> u >> v >> w;
        map[u].push_back(edge(v, w));
    }

    q.push(std::make_pair(0, start));
    min_distance[start] = 0;

    while (!q.empty())
    {
        edge current = q.top();
        q.pop();
        int c_v = current.second;
        if (visited[c_v] == 1)
            continue;
        visited[c_v] = 1;

        for (int i = 0; i < map[c_v].size(); ++i)
        {
            edge tmp = map[c_v][i];
            int next = tmp.first;
            int value = tmp.second;

            if (min_distance[next] > min_distance[c_v] + value)
            {
                min_distance[next] = min_distance[c_v] + value;
                q.push(std::make_pair(min_distance[next], next));
            }
        }
    }

    for (int i = 1; i <= V; ++i)
    {
        if (visited[i] == 0)
            std::cout << "INF" << "\n";
        else
            std::cout << min_distance[i] << "\n";
    }                

    return 0;
}

 

💡알게 된 것 

 - 간만에 다시 한 알고리즘 문제
 - 다익스트라에 대해서 다시 리마인드 할 수 있었다.
 - 큐에 넣어서 진행시키는걸 알고리즘 간만에 하느라 까먹었었다.. 우선순위 큐 (priority_queue)도 너무 간만이라 낯설었다.. 종종해야지 ㅠ

---