[Algorithm]Baekjoon 1916번 :: 최소비용 구하기

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

1916번: 최소비용 구하기

struct Node
{
    int city;
    int distance;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.distance > b.distance;
    }
};
 
int n, m;
int start, dest;
 
vector<vector<Node>> graph;
int dist[1001];
 
void dij()
{
    int result = 0;
    dist[start] = 0;
 
    priority_queue<Node,vector<Node>, cmp> pq;
    pq.push({ start,0 });
 
    while (!pq.empty())
    {
        Node curNode = pq.top();
        pq.pop();
 
        int city = curNode.city;
        int distance = curNode.distance;
 
        if (distance > dist[city]) continue;
 
        for (int i = 0; i < graph[city].size(); i++)
        {
            int nextCity = graph[city][i].city;
            int nextDistance = distance + graph[city][i].distance;
 
            if (nextDistance < dist[nextCity])
            {
                dist[nextCity] = nextDistance;
                pq.push({ nextCity,nextDistance });
            }
        }
    }
 
    cout << dist[dest];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int a, b, c;
    memset(dist, 0x3f, sizeof(dist));
 
    cin >> n >> m;
 
    graph.resize(n + 1);
 
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
    }
 
    cin >> start >> dest;
    dij();
}

다익스트라의 기본문제이다.

오랜만에 다시 풀고나니, 다익스트라에 대한 로직,코드가 완전히 머리에 박힌 느낌이다.

 

while문 안에 if (distance > dist[city]) continue;

라는 코드같은 경우, 이미 다른 노드를 작업하는 과정에서 배열에 최단거리가 업데이트가 되어있을 수 있기 때문이다.

그런 경우에는 굳이 작업을 수행할 필요가 없기 때문에 바로 continue하는것이다.

물론 없어도 답은 구해지지만, 이번 문제같은 경우에는 시간제한이 상당히 짧기 때문에 저 코드가 없다면 시간초과가 발생하기 때문에 반드시 검사해줘야 한다.