1708 問(wèn)題 I: 數(shù)據(jù)結(jié)構(gòu)-Dijskra(迪杰斯特拉)最短路徑算法
時(shí)間限制: 1s
內(nèi)存限制: 32MB 提交: 2062 解決: 893
題目描述
在帶權(quán)有向圖G中，給定一個(gè)源點(diǎn)v，求從v到G中的其余各頂點(diǎn)的最短路徑問(wèn)題，叫做單源點(diǎn)的最短路徑問(wèn)題。
在常用的單源點(diǎn)最短路徑算法中，迪杰斯特拉算法是最為常用的一種，是一種按照路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。
可將迪杰斯特拉算法描述如下：
在本題中，讀入一個(gè)有向圖的帶權(quán)鄰接矩陣（即數(shù)組表示），建立有向圖并按照以上描述中的算法求出源點(diǎn)至每一個(gè)其它頂點(diǎn)的最短路徑長(zhǎng)度。
輸入
輸入的第一行包含2個(gè)正整數(shù)n和s，表示圖中共有n個(gè)頂點(diǎn)，且源點(diǎn)為s。其中n不超過(guò)50，s小于n。
以后的n行中每行有n個(gè)用空格隔開的整數(shù)。對(duì)于第i行的第j個(gè)整數(shù)，如果大于0，則表示第i個(gè)頂點(diǎn)有指向第j個(gè)頂點(diǎn)的有向邊，且權(quán)值為對(duì)應(yīng)的整數(shù)值；如果這個(gè)整數(shù)為0，則表示沒(méi)有i指向j的有向邊。當(dāng)i和j相等的時(shí)候，保證對(duì)應(yīng)的整數(shù)為0。
輸出
只有一行，共有n-1個(gè)整數(shù)，表示源點(diǎn)至其它每一個(gè)頂點(diǎn)的最短路徑長(zhǎng)度。如果不存在從源點(diǎn)至相應(yīng)頂點(diǎn)的路徑，輸出-1。
請(qǐng)注意行尾輸出換行。
樣例輸入
4 1 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0
樣例輸出
6 4 7
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情
比賽公告
自主練習(xí)！第一次練手。
針對(duì)基本算法，概況的20題。
有難題，新題，或經(jīng)典題。
排序算法、高精度算法。