題意不說了筋岛，有特殊要求的最短路。對(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)妥的方法依溯，多寫幾行代碼老厌，比如記錄下所有的路徑，之后再作判斷黎炉。
