一、题目：

洛谷原题

二、思路：

这是暴力做法，正解请看下一篇。 floyd（传递闭包）+ SPFA。 用传递闭包标记哪些点和终点联通，然后跑SPFA，在判断点是否入队是增加一条判断条件——是否与终点连通。

Tips：在这道题中，SPFA的实质是BFS，我习惯叫它为SPFA。

注意起点的特判。 得分：60分。

三、代码：

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; inline int read(void) { int x = 0, f = 1; char ch = getchar(); while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } const int maxn = 10005, maxm = 200005; int n, m, head[maxn], tot, start, en, dis[maxn], flag[maxn][maxn]; bool vis[maxn]; struct Edge { int y, next; }e[maxm]; inline void connect(int x, int y) { e[++tot].y = y; e[tot].next = head[x]; head[x] = tot; } inline bool check(int node) { for (register int i = head[node]; i; i = e[i].next) { if (!flag[e[i].y][en])return false; } return true; } inline void init(void) { n = read(); m = read(); for (register int i = 1; i <= m; i++) { int x = read(), y = read(); if (x == y)continue; if (flag[x][y])continue; flag[x][y] = true; connect(x, y); } start = read(); en = read(); for (register int i = 1; i <= n; i++)flag[i][i] = true; for (register int k = 1; k <= n; k++) for (register int i = 1; i <= n; i++) for (register int j = 1; j <= n; j++) flag[i][j] |= (flag[i][k] && flag[k][j]); } inline void solve(void) { queue<int>q; q.push(start); vis[start] = true; memset(dis, 0x3f, sizeof(dis)); dis[start] = 0; while (q.size()) { int u = q.front(); q.pop(); vis[u] = false; for (register int i = head[u]; i; i = e[i].next) { int y = e[i].y; if (dis[y] > dis[u] + 1 && check(y)) { dis[y] = dis[u] + 1; if (!vis[y]) { q.push(y); vis[y] = true; } } } } if (dis[en] == 0x3f3f3f3f) { puts("-1"); } else printf("%d\n", dis[en]); } int main() { init(); if (!flag[start][en]) { puts("-1"); return 0; } solve(); return 0; }