这么简单的题都想了半天,肯定是智商低
看起来对Floyd的掌握还不够熟练呢
总之,把2^k的状态扔在最外围循环就ok了
// luogu-judger-enable-o2#include#include #include #include using namespace std;const int MAXN = 50 + 2;int N, M;bool d[MAXN][MAXN][63];int f[MAXN][MAXN];int main(){ cin>>N>>M;memset(f, 0x3f, sizeof(f)); for(int i = 1, u, v; i <= M; i++){ scanf("%d%d", &u, &v); d[u][v][0] = 1, f[u][v] = 1; } for(int p = 1; p < 63; p++) for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(d[i][k][p - 1] && d[k][j][p - 1]) d[i][j][p] = 1, f[i][j] = 1; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); cout< <