BOJ 1753 최단경로

아이디어

아주 예전에 다익스트라 알고리즘 설명글을 살짝 본 것을 토대로 아이디어를 잡아서 해보려 했으나, 정점과 간선을 어떻게 다루어야 할지 방법이 잘 떠오르지 않았다. 결국 몇번 틀리고 나서(TLE, MLE) 해답을 보고 한참을 고민해서 AC 할 수 있었다. 항상 가장 최단거리의 간선을 먼저 선택해야 최단거리를 계속 갱신할 수 있기 때문에 간선을 선택하는 순서를 잘 고르는 것인 관건이었다. 이는우선순위큐를 활용해서 했다. 사실 해답을 보고도 한참을 고민하다가 머리 좀 식혀야겠다 하고 밥먹고 누워있다가 가만히 고민해보니 금방 정리가 됐었다. 알고리즘은 항상 자기 전이나 누워서 가만히 생각할 때 아이디어가 툭 튀어나온다.

 

문제풀이

다익스트라 + 우선순위 큐

#include<bits/stdc++.h>
#define INF 987654321

using namespace std;

struct Comp{
    bool operator()(pair<int, int> a, pair<int, int> b){
        return b.second < a.second;
    }
};
vector<vector<pair<int, int>>> vt;

int dist[20001];
int v, e, start;
int from, to, weight; 
int main(){
    cin >> v >> e;
    cin >> start;
    for(int i=0;i<=v;i++){
        vector<pair<int, int>> tmp;
        vt.push_back(tmp);
        dist[i] = INF;
    }

    for(int i=0;i<e;i++){
        cin >> from >> to >> weight;
        vt[from].emplace_back(to, weight);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;

    pq.emplace(start, 0);
    dist[start] = 0;
    while(!pq.empty()){
        int destination = pq.top().first; 
        int cost = pq.top().second;
        pq.pop();
        vector<pair<int, int>> info = vt[destination];
        for(int i=0;i<info.size();i++){
            pair<int, int>& next = info[i];
            if (cost + next.second < dist[next.first]) {
                dist[next.first] = cost + next.second;
                pq.emplace(next.first, cost + next.second);
            }
        }
    }

    for(int i=1;i<=v;i++){
        if(dist[i]==INF) cout << "INF" << "\n";
        else cout << dist[i] << "\n";
    }
}