BF算法的更新思想就是運(yùn)用動(dòng)態(tài)規(guī)劃的思想，省去一維的i時(shí)刻
注意點(diǎn)：
1.選取n條邊揭北，也就是n條邊的中轉(zhuǎn)
2.由于負(fù)權(quán)邊的存在寨辩，因此最后若不存在的話圃庭，返回的不一定是INF锄奢，而是比它稍微小一點(diǎn)的很大的數(shù)
3.備份數(shù)組保證更新上一次的值，而不會(huì)出現(xiàn)串聯(lián)更新的情況
4.bf算法可以用于判斷是否存在負(fù)環(huán)
#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;
//枚舉經(jīng)過(guò)幾條中轉(zhuǎn)
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 站中轉(zhuǎn)內(nèi)最便宜的航班
有 n 個(gè)城市通過(guò) m 個(gè)航班連接拘央。每個(gè)航班都從城市 u 開(kāi)始，以價(jià)格 w 抵達(dá) v书在。
現(xiàn)在給定所有的城市和航班灰伟，以及出發(fā)城市 src 和目的地 dst，你的任務(wù)是找到從 src 到 dst 最多經(jīng)過(guò) k 站中轉(zhuǎn)的最便宜的價(jià)格蕊温。 如果沒(méi)有這樣的路線袱箱，則輸出 -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];
}
};
