[C++]백준 11657

[C++]백준 11657 타임머신 입니다. 벨만-포드 알고리즘을 사용합니다.

[C++]백준 11657 - 타임머신

벨만-포드 알고리즘을 이용하여 푸는 문제입니다.
솔직히 벨만-포드 알고리즘이 어떤 알고리즘인지 모르고 문제를 접하였고 알고리즘을 검색해 보았습니다.

벨만-포드 알고리즘을 이해한 후 알고리즘에 따라 문제를 풀었습니다.

벨만-포드 알고리즘은 최소 값을 구하는 알고리즘인데 다익스트라와 다른 점은 음수 사이클의 노드를 알 수 있다는 점에 있습니다. 이를 통해 음수로 무한히 가는 경우에는 “-1”을 출력 시켜줄 수 있었습니다.

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

#define endl "\n"
#define MAX 501
#define INF 1<<30

struct edge{
  int from;
  int to;
  int cost;
};

int N, M;
long long Dist[MAX];
vector<edge> Edge;


int main() {
  // 입력 부분
  cin >> N >> M;
  for (int i=1; i<=N;i++) Dist[i] = INF;
  for (int i=0; i< M; i++){
    int From, To, Cost;
    edge tmp;
    cin >> tmp.from >> tmp.to >> tmp.cost;

    Edge.push_back(tmp);
  }
  // 벨만-포드 알고리즘 시작 N-1만큼 모든 수 탐색
  Dist[1] = 0;
  for (int i=1; i<=N - 1; i++){
    for(int j=0; j<Edge.size(); j++){
      int From = Edge[j].from;
      int To = Edge[j].to;
      int Cost = Edge[j].cost;

      if (Dist[From] == INF) continue;
      if (Dist[To] > Dist[From] + Cost) Dist[To] =Dist[From] + Cost;
    }
  }
  // 음수 사이클인 노드 확인
  for (int i = 0 ; i < Edge.size(); i++){
      int From = Edge[i].from;
      int To = Edge[i].to;
      int Cost = Edge[i].cost;

    if (Dist[From] == INF) continue;
    if (Dist[To] > Dist[From] + Cost){
      cout << -1 << endl;
      exit(0);
    }
  }
  // 외딴 노드와 최솟값 출력
  for (int i=2; i<=N; i++){
    if (Dist[i] == INF) cout << -1 << endl;
    else cout << Dist[i]<<endl;
  }

  return 0;
}

[C++]백준 11657

Abstract

[C++]백준 11657 - 타임머신