백준, BOJ, 1753번, 최단경로 : C++ [CPP] ★★★★★

어렵다.

다익스트라를 배웠지만

코딩테스트에서 다시 쓰니까 어렵다

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

 

---

 

#맞은 풀이

#include <iostream>
#include <climits>
#include <queue>
#include <vector>
#include <functional>

#define INF INT_MAX

using namespace std;


int V,E,start;

//벡터를 원소로 가지는 배열 -> 
vector <pair<int,int>> adj[20001]; // 인접행렬 from,(weight,to)
//-> adj[1] = {3,5} 의 의미 1번 정점에서 5번으로 가는 가중치 3


//이런 그래프에서 최단거리 => 다익스트라 테이블
int table[20001];

//최소 간선을 위한 minHeap {거리, 정점 번호} -> 일반적으로 first를 기준으로 오름차순으로 정렬함.

/*
void dijkstra(){
    prority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
    table[st] = 0;
    minHeap.push({table[st], st});
}
*/  



int main(){
    
    cin >> V >> E >> start;
    
    //테이블 초기화 최댓값 INF로
    fill(table, table+V+1, INF); //V개만 초기화하면 됨 사실
    
    
    //E개의 간선 정보 업데이트 -> adj에
    for(int i = 0; i<E; i++){
        int from, to, weight;
        cin >> from >> to >> weight;
        adj[from].push_back({weight, to}); // 해당 정점에서 어디로 가느냐
    }
    
    //최소힙 생성
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > minHeap;
    
    table[start] = 0;
    minHeap.push({table[start], start}); //거리, 정점
    while(!minHeap.empty()){
        auto cur = minHeap.top();
        minHeap.pop();
        
        //거리, to를 뽑음
        int dist = cur.first;
        int idx = cur.second;
        //해당 정점에 대한 최단거리 테이블의 정보와 비교해서 조사해야하는지 확인
        if(table[idx] < dist) continue;
        
        //그렇다면 해당 정점이 갈 수 있는 곳을 알아봄
        //adj[from] = {weight, to}
        for(auto next : adj[idx]){
            int cost = next.first; //해당 정점에 가는데 드는 가중치
            int nidx = next.second; //갈 수 있는 정점
            //해당 정점이 갈 수 있는 거리 중 table에 있는 것보다 작다면 업데이트
            if(table[nidx] > dist + cost){
                table[nidx] = dist+cost;
                minHeap.push({table[nidx], nidx});
            }
        }
    }
    
    //출력
    for(int i = 1; i <= V; i++){
    if(table[i] == INF) cout << "INF\n";
    else cout << table[i] << "\n";
  }
    
}

 

이와 비슷한 문제를 조금 더 풀어보면서 복습해야겠다.