以p1847为例
spfa算法。。。。
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。 判断有无负环： 如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）
负环还没有接触到。。
这个算法最小距的时候蛮好理解，我有见过它用在最大流
先确定一个距离数组dis,记录的是某个点s到所有的点的最短距，开始时先把点放到一个数组中，然后对于这个点u，开始对所有与它相连的并且dis[i] > dis[u] + mat[u][i]的点i遍历，改变dis[i]的值，并且如果i不在数组中把i放到数组中，注意最后 vis[u] = false;
重复执行直到数组为空。
代码
#include <stdio.h> #define maxN 110 #define inf 1000000000 int mat[maxN][maxN]; bool flag[maxN][maxN]; bool vis[maxN]; int dis[maxN]; int queue[10 * maxN]; int n,a,b; void Init()//初始化 { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { if (i == j) { mat[i][j] = 0; } else mat[i][j] = inf; flag[i][j] = false; } vis[i] = false; dis[i] = inf; } } void spfa() // spfa算法 { int head = 0, tail = 1; queue[head] = a; dis[a] = 0; while (head < tail) { int u = queue[head]; vis[u] = true; for (int i = 1; i <= n; ++ i) { if (flag[u][i] && dis[i] > dis[u] + mat[u][i]) { dis[i] = dis[u] + mat[u][i]; if (!vis[i]) { vis[i] = true; queue[tail] = i; tail ++; } } } vis[u] = false; head ++; } if (dis[b] >= inf) { printf("-1\n"); } else printf("%d\n", dis[b]); } void floyd() //floyd 算法 { for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= n; ++ j) { for (int k = 1; k <= n; ++ k) { if (mat[j][k] > mat[j][i] + mat[i][k]) { mat[j][k] = mat[j][i] + mat[i][k]; } } } } if (mat[a][b] >= inf) { printf("-1\n"); } else printf("%d\n", mat[a][b]); } int main() { while (scanf("%d%d%d", &n, &a, &b) != EOF) { //scanf("%d%d%d", &n, &a, &b); Init(); for (int i = 1; i <= n; ++ i) { int m,v; scanf("%d", &m); for (int j = 0; j < m; ++ j) { scanf("%d", &v); if (j == 0) { mat[i][v] = 0; } else mat[i][v] = 1; //mat[i][v] = !(j == 0); flag[i][v] = true; } } spfa(); } return 0; }
