Bellman-Ford

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];
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末义矛,一起剝皮案震驚了整個(gè)濱河市发笔,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌凉翻,老刑警劉巖了讨,帶你破解...
    沈念sama閱讀 222,865評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡前计,警方通過(guò)查閱死者的電腦和手機(jī)胞谭,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)男杈,“玉大人丈屹,你說(shuō)我怎么就攤上這事×姘簦” “怎么了旺垒?”我有些...
    開(kāi)封第一講書人閱讀 169,631評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)肤无。 經(jīng)常有香客問(wèn)我先蒋,道長(zhǎng),這世上最難降的妖魔是什么宛渐? 我笑而不...
    開(kāi)封第一講書人閱讀 60,199評(píng)論 1 300
  • 正文 為了忘掉前任竞漾,我火速辦了婚禮,結(jié)果婚禮上窥翩,老公的妹妹穿的比我還像新娘业岁。我一直安慰自己,他們只是感情好鳍烁,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,196評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布叨襟。 她就那樣靜靜地躺著,像睡著了一般幔荒。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上梳玫,一...
    開(kāi)封第一講書人閱讀 52,793評(píng)論 1 314
  • 那天爹梁,我揣著相機(jī)與錄音,去河邊找鬼提澎。 笑死姚垃,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的盼忌。 我是一名探鬼主播积糯,決...
    沈念sama閱讀 41,221評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼谦纱!你這毒婦竟也來(lái)了看成?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書人閱讀 40,174評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤跨嘉,失蹤者是張志新(化名)和其女友劉穎川慌,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,699評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡梦重,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,770評(píng)論 3 343
  • 正文 我和宋清朗相戀三年兑燥,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片琴拧。...
    茶點(diǎn)故事閱讀 40,918評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡降瞳,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出蚓胸,到底是詐尸還是另有隱情挣饥,我是刑警寧澤,帶...
    沈念sama閱讀 36,573評(píng)論 5 351
  • 正文 年R本政府宣布赢织,位于F島的核電站亮靴,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏于置。R本人自食惡果不足惜茧吊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,255評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望八毯。 院中可真熱鬧搓侄,春花似錦、人聲如沸话速。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,749評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)泊交。三九已至乳讥,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間廓俭,已是汗流浹背云石。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,862評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留研乒,地道東北人汹忠。 一個(gè)月前我還...
    沈念sama閱讀 49,364評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像雹熬,于是被迫代替她去往敵國(guó)和親宽菜。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,926評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容