spfa判断负环

判断负环的时候都放进去，不一定从那个点开始，五个点有四条边--当边数>=n的时候一定有负环。
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

floyd算法

floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), n 表示点数
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

题目描述
题目描述
给定一个 nn 个点的有向图，请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式
本题单测试点有多组测试数据。

输入的第一行是一个整数 TT，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 nn 和接下来给出边信息的条数 mm。

接下来 mm 行，每行三个整数 u, v, w。

若 w \geq 0w≥0，则表示存在一条从 u 至 vv边权为 ww的边，还存在一条从 v 至 u 边权为 w 的边。
若 w < 0w<0，则只表示存在一条从 u 至 vv 边权为 w 的边。
输出格式
对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

样例
输入：
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出

NO
YES

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N], cnt[N];//记录每个点到起点的边数，当cnt[i] >= n 表示出现了边数>=结点数
//，必然有环，而且一定是负环！
bool st[N];//判断当前的点是否已经加入到队列当中了；
//意味着，st数组起着提高效率的作用，不在乎效率的话，去掉也可以
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()
{
    //初始化所有非起点和起点的距离
    // memset(dist, 0x3f, sizeof dist);
    // dist[1] = 0;
    // 这里不需要初始化dist数组为 正无穷。不用初始化的原因是,如果存在负环那么dist不管初始化为多少都会被更新
    //定义队列，起点进队, 标记进队
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        //判断负环，只从一个点出发，有可能到达不了负环那里
        q.push(i);//需要一开始就把所有结点放入队列，且标记进入了队列降低效率
        st[i] = true;
    }

    //队列中的点用来更新其他点到起点的距离
    while (q.size())
    {
        //取队头，弹队头
        auto t = q.front();
        q.pop();
        //t出队，标记出队
        st[t] = false;

        //更新与t邻接的边
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];//结点j可以通过中间点t降低距离
                cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边

                if (cnt[j] >= n) return true;//边数不小于结点数，出现负环，函数结束

                if (!st[j])//若此时j没在队列中，则进队。已经在队列中了，上面已经更新了数值。重复加入队列降低效率
                {
                    //j进队，标记进队
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;//走到这了，函数还没结束，意味着边数一直小于结点数，不存在负环
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");


    return 0;
}

floyd算法

floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), n 表示点数
初始化：
d[N][N]代表距离
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
    或者
    memset(d,INF,sizeof d);
    for(int i=1;i<=n;i++)d[i][i]=0;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。
数据保证图中不存在负权回路。

输入格式
第一行包含三个整数n，m，k
接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式
共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1

#include<bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

int n,m,q;
int d[N][N];//距离

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int main()
{
    cin>>n>>m>>q;
    memset(d,0x3f,sizeof d);//初始化d数组
    for(int i=1;i<=n;i++) d[i][i]=0;//防止自环，取最小数0，
    while(m--) //邻接矩阵，取权值较小的边
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
    }

    floyd();

    while(q--)
    {
        int a,b;
        cin>>a>>b;

        if(d[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }

    return 0;
}