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

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

1916번: 최소비용 구하기

가중치 유향 그래프에서 시작 정점에서 도착 정점까지의 최소비용을 구하는 문제이다. 

다익스트라와 벨만포드 알고리즘을 사용해서 해결할 수 있다.

다익스트라의 시간 복잡도 O(E+VlogV), 벨만 포드 시간복잡도 O(VE), E:간선, V:정점 수 로 다익스트라의 효율이 더 높다.

 

다익스트라(우선순위 큐)

1. 시작점의 거리를 0으로 초기화 하고 우선순위 큐(최소 힙)에 넣는다.

2. 기존 노드의 거리보다 새로운 길로 돌아온 거리가 더 크다면 그 노드에서는 더 이상 탐색하지 않는다(다른 최소 경로가 존재 함). 따라서, 새로운 거리가 기존보다 같거나 작다면 탐색해본다.

3. 연결 노드에 대해 기존의 거리보다 새로운 길의 거리가 더 작다면 업데이트 하고 push한다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M, A, B, C;

struct Node
{
    int vex, dist;
    Node(int a, int b){ 
        vex=a;
        dist=b;
    }
    bool operator<(const Node& a) const {
        return dist > a.dist;
    }
};

void dijkstra(vector<vector<Node>>& graph, int st, vector<int>& dist)
{
    priority_queue<Node> pq;
    pq.push(Node(st, 0));
    dist[st]=0;

    while (!pq.empty()){
        int node = pq.top().vex;
        int cost = pq.top().dist;
        pq.pop();
        if (dist[node]<cost) continue;

        for (int i=0; i<graph[node].size(); i++){
            int nnode = graph[node][i].vex;
            int ncost = cost + graph[node][i].dist;
            if (dist[nnode] > ncost){
                dist[nnode]=ncost;
                pq.push(Node(nnode, ncost));
            }
        }
    }
}

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

    // freopen("input.txt", "r", stdin);
    cin >> N;
    cin >> M;
    
    vector<vector<Node>> graph(N+1);
    for (int i=0; i<M; i++){
        cin >> A >> B >> C;
        graph[A].push_back(Node(B,C));
    }

    cin >> A >> B;
    vector<int> dist(N+1, 2147000000);
    dijkstra(graph, A, dist);
    cout << dist[B] << endl;
    return 0;
}

벨만포드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M, A, B, C;

struct Node
{
    int from, to, dist;
    Node(int a, int b, int c){ 
        from=a;
        to=b;
        dist=c;
    }
};

void bellman(vector<Node>& graph, int st, vector<int>& dist)
{
    dist[st]=0;
    // 1~N-1개 간선 사용
    for (int i=1; i<N; i++){
        for (int j=0; j<graph.size(); j++){
            int u=graph[j].from;
            int v=graph[j].to;
            int val=graph[j].dist;
            if (dist[u]!=2147000000 && dist[u]+val < dist[v]){
                dist[v] = dist[u]+val;
            }
        }
    }
}

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

    // freopen("input.txt", "r", stdin);
    cin >> N;
    cin >> M;
    
    vector<Node> graph;
    for (int i=0; i<M; i++){
        cin >> A >> B >> C;
        graph.push_back(Node(A,B,C));
    }

    cin >> A >> B;
    vector<int> dist(N+1, 2147000000);
    bellman(graph, A, dist);
    cout << dist[B] << endl;
    return 0;
}