BOJ 16763 - Fine Dining

BOJ 16763 - Fine Dining

단순 최단경로 문제이지만 생각을 좀 해야한다.

일단 $N$ 에서부터의 각 정점까지의 최단 경로를 구한다.

그리고 어떤 haybale이 있는 지점 $j$ 를 거쳐가는 최단 경로는 다음과 같다.

$D_{i, j}+D_{j,N}$

그러면 문제에서 요구하는 식은 결국

$$ \begin{aligned} D_{i,j}+D_{j,N}-Y_j \le D_{i,N}\\ D_{j,N}-Y_j \le D_{i,N} - D_{i,j} \end{aligned} $$

를 만족하는 $j$ 가 각 $i$ 에 대해 있는지 찾으라는 것이고,

각 $j$ 들의 시작점의 최단 거리를 $D_{j,N}-Y_j$ 으로 두고 최단 경로를 한 번 더 돌렸을 때 $D_{i,j}$ 가 원래 $D_{i,N}$ 이하를 만족하게 되면 $1$을 출력해주면 된다.

$j$ 가 실제로 뭔진 몰라도 각 $j$ 에서부터 최단 경로를 찾기 시작했으므로 (multi source bfs), $D_{i,j}$ 중 최솟값이 $i$ 에 저장이 되게 돌려줄 수 있다.

void solve() {
   int n, m, k;
   cin >> n >> m >> k;
   vector<vector<pi>> edges(n);
   for (int i = 0, a, b, t; i < m; i++) cin >> a >> b >> t, a--, b--, edges[a].pb({b, t}), edges[b].pb({a, t});
   vi dist(n, 2e15);
   queue<int> q;
   q.push(n - 1);
   dist[n - 1] = 0;
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (auto [to, w]: edges[cur]) {
         if (dist[to] > dist[cur] + w) {
            dist[to] = dist[cur] + w;
            q.push(to);
         }
      }
   }
   vi dist2(n, 2e15);

   for (int i = 0, j, yy; i < k; i++) {
      cin >> j >> yy, j--;
      dist2[j] = dist[j] - yy;
      q.push(j);
   }
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (auto [to, w]: edges[cur]) {
         if (dist2[to] > dist2[cur] + w) {
            dist2[to] = dist2[cur] + w;
            q.push(to);
         }
      }
   }
   for (int i = 0; i < n - 1; i++) {
      if (dist2[i] <= dist[i]) cout << 1 << endl;
      else cout << 0 << endl;
   }
}