[백준] 1219번 오민식의 고민

March 15, 2021 ( last updated : March 15, 2021 )
벨만포드 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 1219번 오민식의 고민

[백준] 1219번 오민식의 고민

백준 1219번

벨만 포드 알고리즘 문제 중 하나입니다. 벨만 포드는 그래프 탐색 알고리즘 중 하나로 각 노드에 대한 최적의 비용을 할 수 있습니다.

다익스트라 알고리즘이 이와 비슷한데 벨만 포드 알고리즘은 다익스트라 알고리즘과 다른 점은 비용이 한 없이 낮아져 음의 무한대로 도달 할 때 해당 노드를 알 수 있다는 점입니다.

해당 문제는 대체적으로 일반적인 벨만 포드 알고리즘을 따르지만 주의해야 할 점은 문제의 모든 결과 값은 시작 노드에서 도착 노드까지 도착했을 경우를 상정하고 있습니다. 따라서 해당 조건에 유의하면서 코드를 짜야하며 하단의 코드에는 bfs라는 함수가 해당 조건을 처리하는 역할을 하고 있습니다.

input = 입력 값을 받아주는 함수
bf = 벨만포드
bfs = 도착 가능한지 조건을 확인하는 함수로 bfs를 이용하여 구현

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

#define INF 1LL << 60
#define MAX 101
using namespace std;

typedef struct Edge {
  int from;
  int to;
  long long cost;
} Edge;

int N, S, E, M;
vector<Edge> VEC;
long long DIST[MAX], EARN[MAX];
int is_visited[MAX];

void input();
void bf();
int bfs(int start);

int main() {

  input();
  bfs(S);
  DIST[S] = -EARN[S];
  bf();

  if (DIST[E] != INF)
    cout << -DIST[E];

  return 0;
}

void input() {
  cin >> N >> S >> E >> M;

  for (int i = 0; i < M; i++) {
    Edge edge;
    cin >> edge.from >> edge.to >> edge.cost;
    VEC.push_back(edge);
  }

  for (int i = 0; i < N; i++) {
    DIST[i] = INF;
    cin >> EARN[i];
  }
}

void bf() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      int from = VEC[j].from;
      int to = VEC[j].to;
      long long cost = VEC[j].cost;

      if (DIST[from] == INF) {
        continue;
      }
      if (DIST[to] > DIST[from] + (cost - EARN[to])) {
        DIST[to] = DIST[from] + (cost - EARN[to]);
        if (i == (N - 1) && bfs(to)) {
          cout << "Gee";
          exit(0);
        }
      }
    }
  }
}

int bfs(int start) {
  memset(is_visited, 0, sizeof(is_visited));
  int flag = 0;

  queue<int> q;
  q.push(start);
  is_visited[start] = 1;

  while (!q.empty()) {
    int node = q.front();

    q.pop();

    for (int i = 0; i < M; i++) {
      if (VEC[i].from != node)
        continue;
      if (!is_visited[VEC[i].to]) {
        is_visited[VEC[i].to] = 1;

        q.push(VEC[i].to);
      }
    }
  }
  if (!is_visited[E]) {
    flag = 1;
    if (start == S) {
      cout << "gg";
      exit(0);
    }
  }
  if (flag) {
    return 0;
  }
  return 1;
}

Originally published March 15, 2021
Latest update March 15, 2021

Related posts :

{# #}