문제

문제 링크 : https://www.acmicpc.net/problem/11657 (단계별로 풀어보기 : 최단 경로)

문제 풀이

일단 해당 문제가 벨만포드 알고리즘을 사용하는 문제라는 것을 알고 있고, 벨만포트 알고리즘을 처음 접하여 구글링을 하여 공부하고 문제를 풀기 시작했다. 나처럼 벨만포드 알고리즘을 처음 접한다면 해당 링크에서 잘 설명되어 있다.
알고리즘을 공부한 후 문제를 봤을 때는 벨만포드 알고리즘을 구현만 하면 된다.
벨만포드 알고리즘 구현은 다음처럼 하면 되겠다.

1. 출발노드 설정
2. 최단거리 테이블(distance[1-N]) 초기화
3. 모든 간선을 보며 최단거리 테이블 갱신 ( N(노드개수) 만큼 반복)
	-> N번째 반복할 때 최단거리 테이블이 갱신되면 음수 순환이 존재.

구현 하면서 애먹은 점은 다음 두가지 였다.

1. 처음 distance를 int형으로 놨는데 다시 생각해보니 long long형을 써야 맞다.
2. 도착 못하는 지점은 -1을 출력해야한다는 것을 빠뜨렸다.

알고리즘 스케치

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define INF 2000000000
#define ll long long
using namespace std;

typedef struct{
    int u;
    int v;
    int cost;
}edge;
vector <edge> edges;
vector <ll> dist;
int N,M;

void input();
int bellman_ford(int start);

int main()
{
    input();
    if(bellman_ford(1)) cout << -1;
    else{
        for(int i=2; i<=N; i++){
            if(dist[i]!=INF)
                cout << dist[i] << "\n";
            else
                cout << -1 << "\n";
        }
    }   
}

void input()
{
    edge tmp;
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> tmp.u >> tmp.v >> tmp.cost;
        edges.push_back(tmp);
    }
    dist.resize(N+1);
    fill(dist.begin(),dist.end(),INF);
}

int bellman_ford(int start) 
{
    dist[start] = 0;
    int cur_node, next_node, edge_cost;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cur_node = edges[j].u;
            next_node = edges[j].v;
            edge_cost = edges[j].cost;
            if(dist[cur_node]!=INF && dist[next_node] > dist[cur_node] + edge_cost){
                dist[next_node] = dist[cur_node] + edge_cost;
                if(i==N-1) return 1;
            }
        }
    }
    return 0;
}