백준 11657 타임머신 - C++, 벨만포드 알고리즘

11657번: 타임머신

#include <iostream>
#include <vector>
using namespace std;

int n, m;
long long node[501];
vector<pair<pair<int, int>, int>> edge;

void Bellman(){
    // 벨만 포드 알고리즘
    node[1] = 0;
    for(int i = 1; i <= n-1; i++){
        for(int j = 0; j < edge.size(); j++){
            int from, to, cost;
            from = edge[j].first.first;
            to = edge[j].first.second;
            cost = edge[j].second;

            if(node[from] == 999999999)
                continue;
            
            if(node[to] > node[from] + cost)
                node[to] = node[from] + cost;
        }
    }
        //사이클이 있는지 확인하기
    for(int i = 0; i < edge.size(); i++){
        int from, to, cost;
        from = edge[i].first.first;
        to = edge[i].first.second;
        cost = edge[i].second;

        if(node[from] == 999999999)
            continue;
            
        if(node[to] > node[from] + cost){
            printf("-1\n");
            return;
        }
            
    }

    // 출력
    for(int i = 2; i <= n; i++){
        if(node[i] == 999999999)
            printf("-1\n");
        else
            printf("%d\n", node[i]);
    }
}

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 0; i <= n; i++)
        node[i] = 999999999;

    for(int i = 0; i < m; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        edge.push_back(make_pair(make_pair(from, to), cost));
    }

    Bellman();
}

---

 처음으로 써본 벨만-포드 알고리즘입니다. 입력을 전부 받은 뒤 각 노드까지 가는 비용을 999999999로 초기화 해줍니다. 이후 벨만포드를 진행을 하면 됩니다.

void Bellman(){
    // 벨만 포드 알고리즘
    node[1] = 0;
    for(int i = 1; i <= n-1; i++){
        for(int j = 0; j < edge.size(); j++){
            int from, to, cost;
            from = edge[j].first.first;
            to = edge[j].first.second;
            cost = edge[j].second;

            if(node[from] == 999999999)
                continue;
            
            if(node[to] > node[from] + cost)
                node[to] = node[from] + cost;
        }
    }
        //사이클이 있는지 확인하기
    for(int i = 0; i < edge.size(); i++){
        int from, to, cost;
        from = edge[i].first.first;
        to = edge[i].first.second;
        cost = edge[i].second;

        if(node[from] == 999999999)
            continue;
            
        if(node[to] > node[from] + cost){
            printf("-1\n");
            return;
        }
            
    }
}

 벨만포드 알고리즘의 순서를 먼저 보겠습니다.

 

1. 처음 순회를 할 때는 시작 지점에서 갈 수 있는 지점을 탐색합니다.

    - 갈 수 없는곳은 node값이 999999999이라 continue처리

2. 이런식으로 하나씩 찾아보면서 각 노드를 방문하는데 걸리는 비용 저장

 

3. 순회를 한번 다 하면 한번 더 순회를 돌아 값이 갱신되는 경우가 있는지 판단

    - 값이 갱신된다는건 비용을 줄일 수 있는 음수 사이클이 있다는 이야기입니다.

 

이런 식으로 벨만-포드를 진행해 음수 사이클일경우 -1을 출력하는 방식으로 진행을 했습니다.