01738번 골목길

Problem link: https://www.acmicpc.net/problem/1738

Keywords: Bellman Ford Algorithm

금품을 주울 때 해당 골목(간선)의 가중치를 음수로, 금품을 갈취 당할 때 해당 골목의 가중치를 양수로 표현한 뒤에 Bellman-Ford를 사용하면 쉽게 풀 수 있다. 다만, 여느 Bellma-Ford를 쓰는 문제들과 같이 음수 사이클이 생기는 경우를 잘 생각해서 처리해주어야한다. 이 문제에서 음수 사이클이 생긴다고 다짜고짜 -1을 출력하면 WA를 받게되므로 주의하자. 최적해가 존재하지 않아서 -1을 출력해야하는 상황은 아래와 같다.

그래프 내에 음수 사이클이 존재하며,
1번 정점에서 음수 사이클 내의 임의의 정점으로 갈 수 있고,
음수 사이클 내의 임의의 정점에서 N번 정점으로 갈 수 있다.

첫번째 bullet은 간선의 relaxation 횟수를 살펴서 쉽게 처리할 수 있고, 두/세번째 bullet은 연결성 여부를 판단하기 위해 DFS나 BFS를 수행해주어야 한다. 내 경우에는 Bellman-Ford의 N번째 relaxation에서 relax된 간선의 정점들을 저장해두었기 때문에(이들이 곧 사이클 내부의 정점들이므로), 간편하게 multi-source, multi-destination search를 진핼할 수 있는 BFS를 사용하였다.

정말 별 것은 아니지만, 최적 경로를 backtrack하여 보여주는 과정은 간선 (u, v)가 relaxation될 때 prev[v]에 u를 저장해두는 것을 통해 처리할 수 있다. prev[x]에 마지막에 저장된 값이 결국 최적 경로에서 x의 predecessor가 되는 아이디어를 이용한 것이다.

#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

// Inputs.
constexpr int kMaxDist = 1'000'000;
int N;
int M;
vector<vector<pair<int, int>>> ADJ;

// Solution.
vector<int> DIST;
vector<int> PREV;
set<int> VERTICES_IN_CYCLE;
vector<bool> VISITED;

bool Bfs(const set<int>& sources, const set<int>& destinatios) {
  VISITED.assign(N, false);
  queue<int> q;
  for (int source : sources) {
    VISITED[source] = true;
    if (destinatios.find(source) != destinatios.end()) {
      return true;
    }
    q.emplace(source);
    while (!q.empty()) {
      const auto& here = q.front();
      q.pop();
      for (const auto& [there, _] : ADJ[here]) {
        if (!VISITED[there]) {
          VISITED[there] = true;
          if (destinatios.find(there) != destinatios.end()) {
            return true;
          }
          q.emplace(there);
        }
      }
    }
  }
  return false;
}

void Solve() {
  DIST[0] = 0;
  PREV[0] = -1;
  int it;
  for (it = 0; it < N; ++it) {
    bool has_relaxed = false;
    for (int u = 0; u < N; ++u) {
      for (const auto& [v, w] : ADJ[u]) {
        if (DIST[u] - w < DIST[v]) {
          has_relaxed = true;
          DIST[v] = DIST[u] - w;
          PREV[v] = u;
          if (it == N - 1) {
            VERTICES_IN_CYCLE.insert(u);
          }
        }
      }
    }
    if (!has_relaxed) {
      break;
    }
  }
  if (!VERTICES_IN_CYCLE.empty() && Bfs({0}, VERTICES_IN_CYCLE) &&
      Bfs(VERTICES_IN_CYCLE, {N - 1})) {
    cout << -1 << endl;
  } else {
    stack<int> path;
    int v = N - 1;
    while (PREV[v] != -1) {
      path.push(v);
      v = PREV[v];
    }
    path.push(v);
    while (!path.empty()) {
      cout << path.top() + 1 << ' ';
      path.pop();
    }
  }
}

int main() {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read inputs.
  cin >> N >> M;
  ADJ.assign(N, {});
  DIST.assign(N, kMaxDist);
  PREV.assign(N, -1);
  for (int it = 0; it < M; ++it) {
    int u, v, w;
    cin >> u >> v >> w;
    ADJ[u - 1].push_back({v - 1, w});
  }

  // Solve.
  Solve();

  return 0;
}