Bellman_Ford 算法（解决负权回路，边数限制的最短距离）

852. spfa判断负环

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n

和 m

。

接下来 m

行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z

。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

1≤n≤2000

,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000

。

输入样例：

输出样例：

Yes

/**
* 松弛定理：d[u]+w < d[v] ;
*
* Bellman_Ford 算法：经过Nv-1 条边松弛，求得从源点到达各点的最短路；
* 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
* 一定是没有回路的，因为假设是正回路，那么去掉这条这条回路，一定
* 能得到更短的距离，如果是负回路，那么一定得不到最短路；
*
* 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
* 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
*
* 对于要判断是否有负权回路这种情况，即要进行 Nv-1 轮所有边的松弛操作，可以不使用pre数组，
* 因为进行Nv-1轮或者进行Nv轮迭代没什么区别，如果有负权值，那么进行Nv轮迭代以后边还是能够
* 松弛；
*/


/**
 * 松弛定理：d[u]+w < d[v] ;
 * 
 * Bellman_Ford 算法：经过Nv-1 条边松弛，求得从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 一定是没有回路的，因为假设是正回路，那么去掉这条这条回路，一定
 * 能得到更短的距离，如果是负回路，那么一定得不到最短路；
 * 
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 * 
 * 对于要判断是否有负权回路这种情况，即要进行 Nv-1 轮所有边的松弛操作，可以不使用pre数组，
 * 因为进行Nv-1轮或者进行Nv轮迭代没什么区别，如果有负权值，那么进行Nv轮迭代以后边还是能够
 * 松弛；
*/
 
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
typedef pair<int,int> PII;
 
const int maxn = 2010 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
 
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
int Bellman_Ford(int st) //判断图中是否存在回路
{
    fill(d,d+maxn,INF);
    d[st]=0;
    
    for(int k=1;k<Nv;++k)
    {
        for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])
                    d[v]=d[u]+w;
            }
    }
    
    for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])   //还能被松弛，存在负回路
                    return 1; 
            }
            
    return 0; //不存在负回路
}
 
int main()
{
    Read();
    
    if(Bellman_Ford(1))
        puts("Yes");
    else
        puts("No");
    
    return 0;
 
}

接下来的两个题目本来用SPFA算法会更好，但是我想尝试一下用Bellman_Ford算法解决，因此这两个题目我都是用的Bellman_Ford 算法解决的，下一篇博客我会用SPFA算法求解这两个题目。

853. 有边数限制的最短路

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1

号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n

号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k

。

接下来 m

行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z

。

点的编号为 1∼n

。

输出格式

输出一个整数，表示从 1

号点到 n 号点的最多经过 k

条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

1≤n,k≤500

,
1≤m≤10000,
1≤x,y≤n，
任意边长的绝对值不超过 10000

。

输入样例：

输出样例：

* 松弛定理：d[u]+w < d[v] ;
*
* Bellman_Ford 算法：经过Nv-1 条边松弛，求得从源点到达各点的最短路；
* 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
* 一定是没有回路的，因为假设是正回路，那么去掉这条这条回路，一定
* 能得到更短的距离，如果是负回路，那么一定得不到最短路；
*
* 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
* 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
*
* 对于有边数k限制的图，在进行每一轮全部边松弛的时候，要将上一轮迭代的距离数组d拷贝到
* pre数组中，接下来进行边松弛的时候，对于边的起点距离需要用到pre数组，更新终点距离到
* d 数组；因为第一轮只能用到一条边，如果边的起点也用d数组，会使得更新了起点，而后面的
* 边因为起点被更新了，而这条边被松弛了（即更新终点的距离），但实际情况是这条边不能被
* 松弛，仅仅是因为起点被更新了，而在判断终点的时候，没有使用原来的数组，而是用了被更新
* 的数组（能松弛终点这条边，应当还需要再加一条边才可以），画一个简单的图就能理解）；
* 这是我画的一个图的数据：
* data ：
*      4 4 1
        1 2 2
        2 3 3
        2 4 4
        4 3 1


/**
 * 松弛定理：d[u]+w < d[v] ;
 * 
 * Bellman_Ford 算法：经过Nv-1 条边松弛，求得从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 一定是没有回路的，因为假设是正回路，那么去掉这条这条回路，一定
 * 能得到更短的距离，如果是负回路，那么一定得不到最短路；
 * 
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 * 
 * 对于有边数k限制的图，在进行每一轮全部边松弛的时候，要将上一轮迭代的距离数组d拷贝到
 * pre数组中，接下来进行边松弛的时候，对于边的起点距离需要用到pre数组，更新终点距离到
 * d 数组；因为第一轮只能用到一条边，如果边的起点也用d数组，会使得更新了起点，而后面的
 * 边因为起点被更新了，而这条边被松弛了 （即更新终点的距离），但实际情况是这条边不能被
 * 松弛，仅仅是因为起点被更新了，而在判断终点的时候，没有使用原来的数组，而是用了被更新
 * 的数组（能松弛终点这条边，应当还需要再加一条边才可以），画一个简单的图就能理解）；
 * 这是我画的一个图的数据：
 * data ：
 *      4 4 1
        1 2 2
        2 3 3
        2 4 4
        4 3 1
*/
 
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
const int maxn = 2010 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
int pre[maxn];
 
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
int k;
 
void Read() //读入数据
{
    cin >> Nv >> Ne >> k;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
void Bellman_Ford(int st)
{
    fill(d,d+maxn,INF);
    d[st]=0;
    
    for(int i=1;i<=k;++i)
    {
        memcpy(pre,d,sizeof(d));
        for(int u=1;u<=Nv;++u)
        {
            for(int j=0;j<Adj[u].size();++j)
            {
                int v=Adj[u][j].v,w=Adj[u][j].w;
                if(pre[u]+w < d[v])
                    d[v]=pre[u]+w;
            }
        }
    }
}
 
int main()
{
    Read();
    
    Bellman_Ford(1);
    
    if(d[Nv] > INF/2)   //由于有负权边，所以当两个点不能连通的时候，两个点的距离
        puts("impossible");  //会小于INF
    else
        cout << d[Nv] << endl;
    
    return 0;
 
}

851. spfa求最短路

给定一个 n

个点 m

条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1

号点到 n 号点的最短距离，如果无法从 1 号点走到 n

号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n

和 m

。

接下来 m

行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z

。

输出格式

输出一个整数，表示 1

号点到 n

号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105

,
图中涉及边长绝对值均不超过 10000

。

输入样例：

输出样例：

/**
* Bellman_Ford 算法：经过Nv-1 条边松弛，从源点到达各点的最短路；
* 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
* 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
* 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
*
* 对于Bellnan_Ford 算法最坏时间复杂度是 O(NM),但是往往还未达到Nv-1轮松弛前就已经计算出
* 最短路径了，所以我们可以用一个 flag变量来标记此轮松弛操作是否该改变了dis数组的值，如果
* 没有改变，就提前退出，可以减少相当多的时间消耗；

* 我说怎么能AC，原来是保证不会存在负权回路，当有负权回路的时候，该算法一定是最坏时间复杂度；
*/


/**
 * Bellman_Ford 算法：经过Nv-1 条边松弛，从源点到达各点的最短路；
 * 为什么是 Nv-1 条边，因为Nv个没有回路的顶点的图，最多只有Nv-1条边；
 * 如果进行Nv-1条边松弛以后，顶点还能被松弛，则一定存在负权回路；
 * 因此Bellman_Ford 算法可以求解图是否有负权回路存在。
 * 
 * 对于Bellnan_Ford 算法最坏时间复杂度是 O(NM),但是往往还未达到Nv-1轮松弛前就已经计算出
 * 最短路径了，所以我们可以用一个 flag变量来标记此轮松弛操作是否该改变了dis数组的值，如果
 * 没有改变，就提前退出，可以减少相当多的时间消耗；
   
* 我说怎么能AC，原来是保证不会存在负权回路，当有负权回路的时候，该算法一定是最坏时间复
* 杂度；
*/
 
 
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
struct ENode
{
    int v,w;
};
 
typedef pair<int,int> PII;
 
const int maxn = 1e5+10 ,INF=1e9;
vector<ENode> Adj[maxn]; //邻接表int d[maxn]; 
int d[maxn]; //距离数组
bool hs[maxn]; //记录顶点是否被选择
int Nv,Ne; //顶点数，边数
 
void Read() //读入数据
{
    cin >> Nv >> Ne;
    for(int i=0;i<Ne;++i)
    {
        int u,v,w;
        cin >> u >> v >> w;
        Adj[u].push_back({v,w});
    }
}
 
void Bellman_Ford(int st) //各点到st顶点的最短距离
{
    fill(d,d+maxn,INF);
    d[st]=0;
    
    for(int k=1;k<Nv;++k)
    {
        int flag=0;
        for(int u=1;u<=Nv;++u)
            for(int i=0;i<Adj[u].size();++i)
            {
                int v=Adj[u][i].v,w=Adj[u][i].w;
                if(d[u]+w < d[v])
                {
                    d[v]=d[u]+w;
                    flag=1;
                }
            }
        if(flag == 0)
            break;
    }
}
 
int main()
{
    Read();
    
    Bellman_Ford(1);
    
    if(d[Nv] > INF/2)
        puts("impossible");
    else 
        cout << d[Nv] << endl;
 
    return 0;
    
}

相关阅读:
Selenium Web自动化测试 —— 高级控件交互方法！
OnlineJudge平台（负载均衡）
GTS 中testPersistentProcessMemory fail 详解
 瀑布式开发和敏捷开发
 2022牛客蔚来杯第五场KBHDCG
vue前端导出Excel
基于VUE + Echarts 实现可视化数据大屏环保可视化
 html清楚浮动
 网易云签到可抽奖？那一年我能签到365天。不信？你看。
ROS2学习
原文地址：https://blog.csdn.net/qq_51825761/article/details/126755961