Bellman-Ford

BF算法的更新思想就是运用动态规划的思想，省去一维的i时刻

注意点：

• 1.选取n条边，也就是n条边的中转

• 2.由于负权边的存在，因此最后若不存在的话，返回的不一定是INF，而是比它稍微小一点的很大的数

• 3.备份数组保证更新上一次的值，而不会出现串联更新的情况

• 4.bf算法可以用于判断是否存在负环

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=1e4+10,M=510;
const int INF=0x3f3f3f3f;

int n,m,k;
int dis[M],backup[M];


struct node
{
  int a,b,c;  
}edges[N];

void bf()
{
    memset(dis,INF,sizeof dis);
    dis[1]=0;
    //枚举经过几条中转
    for(int i=0;i<k;i++)
    {
    //枚举所有边，是否能路径压缩
        memcpy(backup,dis,sizeof dis);
        for(int j=0;j<m;j++)
        {
            auto e=edges[j];
            dis[e.b]=min(dis[e.b],backup[e.a]+e.c);
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edges[i]={a,b,c};
    }
    
    bf();
    
    if(dis[n]>INF/2) printf("impossible\n");
    else    printf("%d\n",dis[n]);
    
    return 0;
}

787. K 站中转内最便宜的航班

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

class Solution {
public:
    const int N=110;
    const int INF=0x3f3f3f3f;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
       int dis[N],backup[N];
       memset(dis,INF,sizeof dis);
       dis[src]=0;
        for(int i=0;i<K+1;i++)
        {
            memcpy(backup,dis,sizeof dis);
            for(int j=0;j<flights.size();j++)
            {
                int u=flights[j][0];
                int v=flights[j][1];
                int w=flights[j][2];
                dis[v]=min(dis[v],backup[u]+w);
            }
        }
      if(dis[dst]>INF/2) 
            return -1;
      else
            return dis[dst];
    }
};