BOJ 23258 - 밤편지

BOJ 23258 - 밤편지

플로이드 와샬의 어려운 응용이다.

$2^C$ 이상 먹지 못한다는 것은 $2^{C-1}$ 만 있는 집들은 어떻게 방문하든 상관이 없다는 뜻이다.

따라서 $1 \to N$ 까지 플로이드 와샬을 돌려주며 현재 $2^X$ 짜리를 edge relaxtion 을 쭉 돌려준 후에 오프라인 쿼리로 $C$가 작은것부터 현재 처리되어야 할 것을 처리되고 넘기면 된다.

const int inf = 2e12;
void solve() {
   int n, q;
   cin >> n >> q;
   vvi d(n, vi(n));
   vi ans(q);
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         cin >> d[i][j];
         if (d[i][j] == 0 && i != j) d[i][j] = inf;
      }
   }
   vector<array<int, 4>> qry(q);
   for (int i = 0; i < q; i++) {
      cin >> qry[i][0] >> qry[i][1] >> qry[i][2];
      qry[i][0]--;
      qry[i][1]--, qry[i][2]--, qry[i][3] = i;
   }
   sort(all(qry));

   int qi = 0;
   while (qi < q && qry[qi][0] <= 0) {
      ans[qry[qi][3]] = d[qry[qi][1]][qry[qi][2]];
      qi++;
   }
   for (int c = 0; c < n; c++) {
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            if (d[i][c] == inf || d[c][j] == inf || i == j) continue;
            mina(d[i][j], d[i][c] + d[c][j]);
         }
      }
      // 2^c 를 먹는 집까지 모두 거칠 수 있을 때
      // 합은 최대 2^(c+1) 이상이 될 수 없다.

      while (qi < q && qry[qi][0] <= c + 1) {
         ans[qry[qi][3]] = d[qry[qi][1]][qry[qi][2]];
         qi++;
      }
   }
   for (int i = 0; i < q; i++) cout << (ans[i] == inf ? -1 : ans[i]) << endl;
}