題意不說了筋岛,有特殊要求的最短路。對(duì)于單源最短路晒哄,我是無腦上SPFA睁宰,SPFA也寫了不下十遍,然而這次沒有處理好寝凌。關(guān)于SPFA柒傻,多說幾句,個(gè)人感覺就是優(yōu)化的BFS较木,優(yōu)化在哪了呢红符?就是對(duì)入隊(duì)的節(jié)點(diǎn)有標(biāo)準(zhǔn),只有對(duì)當(dāng)前狀態(tài)可能有幫助的節(jié)點(diǎn)才會(huì)入隊(duì)伐债,有一種“松弛”的感覺预侯,而且個(gè)人感覺這其實(shí)是建一棵樹的過程。
然而這次在25分卡了好久峰锁,最后總算想到了自己哪里沒考慮周全萎馅,這里是AC代碼。題中說如果最短路不止一條祖今,取換乘最少的校坑,此結(jié)果唯一。我的做法是dis數(shù)組保存距離千诬,cnt數(shù)組保存換乘次數(shù)耍目,preS保存前驅(qū)車站,preL保存前驅(qū)線路id徐绑。對(duì)于隊(duì)首的節(jié)點(diǎn)邪驮,對(duì)其相連的點(diǎn)做松弛操作,而這里就是關(guān)鍵傲茄。距離變短了毅访,肯定要松弛(修改前驅(qū))并入隊(duì);距離不變盘榨,但換乘變少喻粹,肯定也要修改。那距離和換乘都不變的話草巡,要不要入隊(duì)呢守呜?
答案是肯定的。又回到了本題給出的前提,所謂的結(jié)果唯一查乒,但是中間結(jié)果不一定唯一(聯(lián)想到最優(yōu)子結(jié)構(gòu))弥喉。而我最開始卻沒有入隊(duì),也就是代碼第54行玛迄,最初寫的是“<”號(hào)而不是“<=”由境,如下,具體的反例注釋在了代碼最后蓖议。其實(shí)還有個(gè)問題虏杰,這樣會(huì)不會(huì)無限循環(huán)(不停入隊(duì)出隊(duì))?其實(shí)是不會(huì)的拒担,這個(gè)問題留給讀者思考嘹屯。
if (tmp <=cnt[v])
{
……
}
網(wǎng)上大佬們貌似都是清一色的dfs攻询,把整個(gè)路徑都存下來从撼,然后判斷、取舍钧栖、輸出低零,所有的路徑都會(huì)走到,因而不會(huì)出現(xiàn)我這樣的問題拯杠。其實(shí)只有這類“答案不唯一掏婶,但是XXX這樣的答案保證唯一”這種情況下才容易發(fā)生我這樣的錯(cuò)誤。所以教訓(xùn)就是:要么考慮周全潭陪,想清楚最優(yōu)子結(jié)構(gòu)是否唯一雄妥,不唯一怎么辦;要么就采用穩(wěn)妥的方法依溯,多寫幾行代碼老厌,比如記錄下所有的路徑,之后再作判斷黎炉。