Floyd 判断是否一步到达
将一步到达的连变跑 Floyd
- #include < iostream > #include < cstdio > #include < algorithm > #include < cstring > using namespace std;
- const int N = 70;
- const int oo = 999999999;
- bool f[N][N][N];
- int n,
- m,
- now = 1,
- head[N],
- dis[N];
- struct Node {
- int u,
- v,
- w,
- nxt;
- }
- G[N * N];
- int Que[N * 5];
- bool vis[N];
- int U[N][N];#define yxy getchar()#define RR freopen("gg.in", "r", stdin) inline int read() {
- int x = 0,
- f = 1;
- char c = yxy;
- while (c < 0 || c > 9) {
- if (c == -) f = -1;
- c = yxy;
- }
- while (c >= 0 && c <= 9) x = x * 10 + c - 0,
- c = yxy;
- return x * f;
- }
- int main() {
- n = read();
- m = read();
- memset(U, 120, sizeof U);
- for (int i = 1; i <= m; i++) {
- int u = read(),
- v = read();
- f[u][v][0] = 1;
- U[u][v] = 1;
- }
- for (int k = 1; k <= 36; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int t = 1; t <= n; t++) {
- if ((f[i][t][k - 1] == 1) && (f[t][j][k - 1] == 1)) {
- f[i][j][k] = 1;
- U[i][j] = 1;
- }
- }
- for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) if (U[i][k] + U[k][j] >= 0) U[i][j] = min(U[i][j], U[i][k] + U[k][j]);
- cout << U[1][n];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2493738.html