夜間のメッセージ(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までの最短時間
VSk - 1以下の家屋のみを経て、iからkまでの最短時間+24579142以下の家屋、kからjまでの最短時間
に表示されます.
始点と終点はk - 1なので、論理に背かない!
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;
}