[ 백준 1916 ] 최소비용 구하기

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

1916번: 최소비용 구하기

 

모든 비용이 0 이상이고, 최소비용을 구하기 때문에 다익스트라로 해결할 수 있다. 알면 쉽고, 모르면 어려운 문제라고 생각한다. 다익스트라의 구현 방법은 세 가지가 있는데, 나는 가장 비효율적인 방법으로 풀었다. 시간복잡도는 O(N^2)다. 가장 비효율적인 방법으로 푼 이유는 다른 두 방법을 몰랐기 때문이다. 다익스트라에 대한 설명은 알고리즘 파트에서 볼 수 있다. 시간 복잡도가 O(nlogn)인 방법도 정리해놨다. 링크 바로가기!

 

#include <iostream>
#define INF 1000000000
using namespace std;
int visit[1001];
int dist[1001];
int n, m;
int weight[1001][1001];
int from, to, cost;

int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            weight[i][j] = INF;
            if(i == j) weight[i][j] = 0; // 없어도 된다
        }
    }
    
    for(int i = 0; i < m; i++){
        cin >> from >> to >> cost;
        if(weight[from][to] > cost) weight[from][to] = cost;
    }
        
    cin >> from >> to;
    
    
    // 다익스트라 시작
    for(int i = 1; i <= n; i++){
        dist[i] = weight[from][i];
    }
    
    visit[from] = true;
    for(int repeat = 0; repeat < n - 1; repeat++){
        
        int min = INF;
        int current = 0;
        for(int i = 1; i <= n; i++){
            if(dist[i] < min && !visit[i]){
                min = dist[i];
                current = i;
            }
        }
        
        visit[current] = true;
        for(int i = 1; i <= n; i++){
            if(!visit[i])
                if(dist[current] + weight[current][i] < dist[i])
                    dist[i] = dist[current] + weight[current][i];
        }
    }
    
    cout << dist[to] << endl;
    
    return 0;
}