백준 - 밤편지(23258)

1. 문제 링크

밤편지

2. 풀이

이슬 조건 해석

2^1 + 2^2 + 2^3 + ... + 2^(c-1) < 2^c 가 성립합니다.
즉, c미만의 번호를 가진 집만 거쳐가야 합니다.

dp

'dp[k][i][j]는 k이하의 집들만 거쳐가며, i에서 j로 가는 최소 시간' 이라고 정의합시다.
그렇다면
dp[k][i][j]는 min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]라고 식이 도출됩니다.
즉,
k - 1이하의 집들만 거쳐가며 i에서 j로 가는 최소 시간
VS
k - 1이하의 집들만 거쳐가며 i에서 k로 가는 최소 시간 + k - 1이하의 집들만 거쳐가며 k에서 j로 가는 최소 시간
이란 의미입니다.
출발점과 도착점은 k여도 되니까 논리에 위배되지 않습니다!

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, q;
int d[301][301][301];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> q;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> d[0][i][j];

			if (i != j && d[0][i][j] == 0) d[0][i][j] = INF;
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][k][j]);
			}
		}
	}

	int c, s, e;
	while (q--) {
		cin >> c >> s >> e;
        // c미만으로 거쳐야돼서 1을 빼준다.
		cout << (d[c - 1][s][e] == INF ? -1 : d[c - 1][s][e]) << '\n';
	}

	return 0;
}