bellman_ford AcWing 853. 有边数限制的最短路

#include
using namespace std;
 
const int N=510,M=10010;
struct Edge
{
    int a,b,w;
}edges[M];
int dist[N];
int backup[N];
int n,m,k;
 
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j
        {
            auto t=edges[j];
            dist[t.b]=min(dist[t.b],backup[t.a]+t.w);
        }
    }
}
 
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    bellman_ford();
    if(dist[n]>=0x3f3f3f3f/2) puts("impossible");
    else    printf("%d\n",dist[n]);
    return 0;
}

  是一个时间复杂度为km的算法，因为总共两层循环。原理就是更新之后使得满足三角不等式，dist[b]<=dist[a]+w.使用结构体来保存点和边长。首先把距离初始化为正无穷，然后把第一个点的距离初始化为0，题目说了，最多经过k条边，所以循环k次，每一次循环把dist数组存到backup数组里面，主要目的是防止串联。串联的意思是说，假设使用之前更新过的距离，可能会导致因为边数限制（只能最多k条边）距离错误，举例说明就是：1->2->3，1->3，假设k等于1，最多只可以经过一条边，那么我们开始更新完1->2，就不能使用这个更新之后的1->2来更新3,我们要使用没有更新过的距离来更新3.大概是这么个意思。

  然后更新最短距离即可，这个操作称为松弛操作。接着是输入输出，最后有一个问题，为什么是0x3f3f3f3f/2，还是距离说明：假设某个点不可以找到最短路，那么它所对应的最短路是0x3f3f3f3f,假设还有一个点对应的最短路也是0x3f3f3f3f，这两个点之间距离是一个比较小的数字d，那么其中一个点可以表示成0x3f3f3f3f-d，那么就不会输出impossible了，因为我们寻找到它的最短路了，但是实际上它是没有最短路的，发生了矛盾。所以我们需要选取一个比较大的数字，来作为判断标准，笔者试了一下，改成0x3f3f3f3f-5e6作为判断标准也是可以的。

  最后输出的时候，使用

    if(dist[n]>=0x3f3f3f3f-5e6) puts("impossible");

会比较简洁。 

  只有在特定的题目里面才会使用这个算法，大部分时候都是spfa算法优于这个算法