[ZPG TEST 117] 跑路【构图】
一看懵了，求一条路的长度whose二进制位中1的个数最小？什么鬼。
其实这种n这么小的图论题，应该往Floyd上想了。令f(p, i, j)为从i走长度为2^p长度的路能否到j，若能，则在一张新的图上连一条i到j的边。最后bfs就猴了。
#include <cstdio>
#include <cstring>
const int maxn = 55, maxm = 10005, maxe = 90000;
int n, m, t1, t2;
bool f[35][maxn][maxn];
int head[maxn], to[maxe], next[maxe], lb;
int que[maxn], head_, tail, h, stp[maxn];
inline void ist(int aa, int ss) {
to[lb] = ss;
next[lb] = head[aa];
head[aa] = lb;
++lb;
}
int main(void) {
freopen("run.in", "r", stdin);
freopen("run.out", "w", stdout);
memset(head, -1, sizeof head);
memset(next, -1, sizeof next);
memset(stp, -1, sizeof stp);
scanf("%d%d", &n, &m);
while (m--) {
scanf("%d%d", &t1, &t2);
f[0][t1][t2] = true;
ist(t1, t2);
}
for (int p = 1; p < 31; ++p) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
if (f[p][i][j] = f[p - 1][i][k] && f[p - 1][k][j]) {
ist(i, j);
break;
}
}
}
}
}
que[tail++] = 1;
stp[1] = 0;
while (head_ != tail) {
h = que[head_++];
if (h == n) {
break;
}
for (int j = head[h]; j != -1; j = next[j]) {
if (stp[to[j]] == -1) {
stp[to[j]] = stp[h] + 1;
que[tail++] = to[j];
}
}
}
printf("%d
", stp[n]);
return 0;
}