欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Bellman-Ford 求最长路

程序员文章站 2022-05-22 10:36:09
...

洛谷 - P1807
题目传送
题意:
Bellman-Ford 求最长路
Bellman-Ford 求最长路

思路:
只有DAG(有向无环图)才有最长路

最长路其实思想和最短路的思想是一样的,如果没有负权值,那么我们完全可以用dijkstar解决(在枚举当前最短路径的时候,直接枚举最长路径即可)。

但是很不幸,这个题有负权值,那么dij解决不了,如果用floyd的话,看到数据为 1 <= n <= 1500,看到会t掉。所以这里用另外一种方法解决,他就是 Bellman-Ford (时间复杂度为(n*m),也就是点的数量乘边的数量,求单源路径)

算法原理:
才刚刚学,不可能理解得那么透彻,也是通过n-1次枚举中间点来更新现在的最大值,但是对于每个循环每条路的中间点都是不一定相同的(就听我乱扯叭)

行了。。。越说越离谱。。。我只是这样好记点

别人的详解算法

AC代码

#include <bits/stdc++.h>
inline long long read(){char c = getchar();long long x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 1e5 + 10;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const double EEE = exp(1);
const int mod = 1e9+7;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
int uv[N][2],dis[2000],val[N];
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //    freopen("input.txt","r",stdin);
    //    freopen("output.txt","w",stdout);
    int n,m;
    cin >> n >> m;
    fill(dis,dis+2000,-INF);//因为是求最长路,所以赋值为-INF
    dis[1] = 0;
    for(int i = 1;i <= m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        uv[i][0] = a,uv[i][1] = b,val[i] = c;//记录哪个点到哪个的权值
    }
    for(int i = 1;i <= n-1;i++)
        for(int j = 1;j <= m;j++)
            dis[uv[j][1]] = max(dis[uv[j][1]],val[j]+dis[uv[j][0]]);
            //这里就是核心了,通过n-1次枚举中间点来更新
    if(dis[n] != -INF) cout << dis[n] << endl;
    else cout << -1 << endl;//1到n不连通
}