[USACO] 백준 6002 - Job Hunt

https://www.acmicpc.net/problem/6002

힌트

어떤 도시를 도착하든 D원을 벌어야 나갈 수 있다. 시작 도시도 예외는 아니다.

풀이

도시를 잇는 도로와 비행기 노선이 제공될 때 어떻게 하면 큰돈을 벌 수 있을까?

 

비행기를 타는데 소비되는 비용을 음수 가중치라 생각하면 이 문제는 음수 가중치가 있는 그래프에서 최장 경로를 찾는 문제가 된다.

 

C도 220 이하이므로 벨만포드 알고리즘의 사용을 적극 고려해볼 수 있다.

 

다만 돈을 버는 행위는 간선이 아닌 정점에서 일어난다는 것에 유의해야 한다.

 

문제의 상황을 벨만포드로 모델링하기 위해 기존 알고리즘의 구현에서 두 가지 조치를 행하면 된다.

 

1. 시작점의 초기값을 0이 아닌 D로 둔다. D만큼 벌어야 도시를 나갈 수 있기 때문

 

2. 비행기를 탈 때 도착 도시에서 D를 버는 것을 고려해서 가중치를 설정한다. 가령 D가 50이고 1에서 2로 가는 비행기의 비용이 20일 때 1->2로 향하는 가중치는 50 - 20 = 30이 된다.

 

위 사항을 신경써서 구현하면 어렵지 않게 정답을 받을 수 있다.

 

정답 코드 - SPFA

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define NODE_MAX 222
vector<pair<int, int>> graph[NODE_MAX];
long long dist[NODE_MAX];
int node_cnt[NODE_MAX];
bool inq[NODE_MAX];
int d, p, c, f, s;
int jet[222][222];
int work[222][222];

bool spfa(int start, int limit) {
  queue<int> q;
  fill(dist, dist + NODE_MAX, -1e18);
  dist[start] = d;
  inq[start] = 1;
  ++node_cnt[start];
  q.push(start);
  while (q.size()) {
    int cur = q.front();
    q.pop();
    inq[cur] = 0;
    for (auto &node: graph[cur]) {
      int nv = node.first, w = node.second;
      if (dist[cur] + w > dist[nv]) {
        dist[nv] = dist[cur] + w;
        if (!inq[nv]) {
          if (++node_cnt[nv] >= limit) return false;
          inq[nv] = 1;
          q.push(nv);
        }
      }
    }
  }
  return true;
}

void solve()
{
  cin >> d >> p >> c >> f >> s;

  for (int i = 0; i < p; ++i)
  {
    int go, to;
    cin >> go >> to;
    work[go][to] = d;
  }

  for (int i = 0; i < f; ++i)
  {
    int go, to, fee;
    cin >> go >> to >> fee;
    jet[go][to] = fee;
  }

  for (int i = 1; i <= c; ++i)
    for (int j = 1; j <= c; ++j)
      if (jet[i][j] || work[i][j])
        graph[i].push_back({j, d - jet[i][j]}); 

  bool res = spfa(s, c);

  if (!res)
  {
    cout << -1;
    return;
  }

  ll ret = -1e18;

  for (int i = 1; i <= c; ++i)
    ret = max(ret, dist[i]);
  cout << ret;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  solve();
}

제출 기록