1. 項(xiàng)目概述從“旅游巴士”到圖論建模最近在復(fù)盤(pán)CSP-J入門(mén)級(jí)2023年的真題T4“旅游巴士”這道題給我留下了挺深的印象。它不像一些純模擬題那樣直白也不像某些復(fù)雜的動(dòng)態(tài)規(guī)劃那樣讓人望而生畏而是巧妙地將一個(gè)生活化的場(chǎng)景——規(guī)劃旅游巴士路線(xiàn)——轉(zhuǎn)化為了一個(gè)經(jīng)典的圖論問(wèn)題。很多剛接觸信息學(xué)競(jìng)賽的同學(xué)看到“巴士”、“景點(diǎn)”、“開(kāi)放時(shí)間”這些字眼可能會(huì)有點(diǎn)發(fā)懵不知道從何下手。其實(shí)這道題的核心就是在帶有時(shí)間限制的圖中尋找滿(mǎn)足條件的最短路徑本質(zhì)上考察的是對(duì)廣度優(yōu)先搜索BFS算法的靈活應(yīng)用和優(yōu)化。題目描述通常是這樣有一個(gè)旅游景點(diǎn)網(wǎng)絡(luò)包含N個(gè)景點(diǎn)節(jié)點(diǎn)和M條觀(guān)光巴士線(xiàn)路邊。每條線(xiàn)路連接兩個(gè)景點(diǎn)并且巴士通過(guò)這條線(xiàn)路需要花費(fèi)一個(gè)單位時(shí)間。關(guān)鍵的限制來(lái)了每個(gè)景點(diǎn)都有一個(gè)“開(kāi)放時(shí)間”a[i]。你的巴士只能在整點(diǎn)時(shí)間到達(dá)某個(gè)景點(diǎn)并且到達(dá)時(shí)間必須大于等于該景點(diǎn)的開(kāi)放時(shí)間。也就是說(shuō)如果你在時(shí)間t到達(dá)景點(diǎn)i必須滿(mǎn)足t a[i]。如果t a[i]你就必須在這個(gè)景點(diǎn)門(mén)口等待直到時(shí)間a[i]才能進(jìn)入并考慮前往下一個(gè)景點(diǎn)。巴士從1號(hào)景點(diǎn)起點(diǎn)在時(shí)間0出發(fā)目標(biāo)是到達(dá)N號(hào)景點(diǎn)終點(diǎn)我們需要找到到達(dá)終點(diǎn)N的最早可能時(shí)間。理解了這個(gè)模型我們就能拋開(kāi)“旅游”、“巴士”這些外殼看到問(wèn)題的本質(zhì)這是一個(gè)節(jié)點(diǎn)帶有訪(fǎng)問(wèn)時(shí)間限制的最短路問(wèn)題。你不能像在普通無(wú)權(quán)圖中做BFS那樣第一次訪(fǎng)問(wèn)到一個(gè)節(jié)點(diǎn)就認(rèn)為找到了最短路徑因?yàn)榧词鼓愀纭暗竭_(dá)”這個(gè)節(jié)點(diǎn)在圖上走了一條更短的路徑也可能因?yàn)殚_(kāi)放時(shí)間的限制而被迫等待導(dǎo)致實(shí)際“進(jìn)入”節(jié)點(diǎn)的時(shí)間反而比后面走其他路徑來(lái)的更晚。這個(gè)“等待”機(jī)制是這道題區(qū)別于標(biāo)準(zhǔn)BFS的關(guān)鍵也是解題的難點(diǎn)和趣味所在。2. 核心思路解析為什么BFS需要“狀態(tài)”升級(jí)解決圖上的最短路問(wèn)題尤其是邊權(quán)相同本題中通過(guò)每條邊耗時(shí)均為1的情況BFS是我們的首選武器。標(biāo)準(zhǔn)BFS的思路非常清晰從起點(diǎn)開(kāi)始一層一層地?cái)U(kuò)展第一次訪(fǎng)問(wèn)到某個(gè)節(jié)點(diǎn)時(shí)所用的步數(shù)時(shí)間就是最短距離。但這個(gè)方法在“旅游巴士”問(wèn)題里直接套用會(huì)失敗。讓我們來(lái)看一個(gè)簡(jiǎn)單的反例。假設(shè)景點(diǎn)1開(kāi)放時(shí)間a[1]0景點(diǎn)2開(kāi)放時(shí)間a[2]5景點(diǎn)3開(kāi)放時(shí)間a[3]2。路徑有兩條1-2-3 和 1-3。使用標(biāo)準(zhǔn)BFS時(shí)間0從1出發(fā)。可以到達(dá)2和3。對(duì)于景點(diǎn)2到達(dá)時(shí)間t1但a[2]5所以必須等待到時(shí)間5才能“進(jìn)入”2。對(duì)于景點(diǎn)3到達(dá)時(shí)間t1a[3]2所以必須等待到時(shí)間2才能“進(jìn)入”3。標(biāo)準(zhǔn)BFS會(huì)記錄“已訪(fǎng)問(wèn)”節(jié)點(diǎn)。它可能先擴(kuò)展節(jié)點(diǎn)2盡管進(jìn)入時(shí)間是5標(biāo)記2已訪(fǎng)問(wèn)。當(dāng)之后從節(jié)點(diǎn)3進(jìn)入時(shí)間2試圖擴(kuò)展到節(jié)點(diǎn)2時(shí)發(fā)現(xiàn)2已訪(fǎng)問(wèn)就會(huì)跳過(guò)。這就錯(cuò)過(guò)了可能通過(guò)節(jié)點(diǎn)3更早進(jìn)入節(jié)點(diǎn)2的機(jī)會(huì)從3到2到達(dá)時(shí)間可能是3但同樣需要等到5和從1直接到2的進(jìn)入時(shí)間一樣。但更重要的是它可能錯(cuò)過(guò)更優(yōu)的全局路徑。問(wèn)題的根源在于在標(biāo)準(zhǔn)BFS中我們用一個(gè)布爾數(shù)組vis[node]來(lái)標(biāo)記節(jié)點(diǎn)是否被訪(fǎng)問(wèn)過(guò)。這隱含了一個(gè)假設(shè)“第一次訪(fǎng)問(wèn)該節(jié)點(diǎn)的路徑就是最優(yōu)的”。但在本題中“最優(yōu)”的標(biāo)準(zhǔn)不是“到達(dá)”節(jié)點(diǎn)的時(shí)刻而是“進(jìn)入”節(jié)點(diǎn)即滿(mǎn)足t a[node]的時(shí)刻。一條更早“到達(dá)”的路徑可能因?yàn)榈却a(chǎn)生更晚的“進(jìn)入”時(shí)間一條稍晚“到達(dá)”的路徑可能因?yàn)榈却龝r(shí)間短而產(chǎn)生更早的“進(jìn)入”時(shí)間。因此我們需要升級(jí)BFS的“狀態(tài)”。我們不能只記錄“是否到過(guò)某個(gè)節(jié)點(diǎn)”而需要記錄“在某個(gè)特定時(shí)間是否進(jìn)入過(guò)某個(gè)節(jié)點(diǎn)”。但是時(shí)間可能很大題目中a[i]最大可達(dá)10^6記錄所有時(shí)間點(diǎn)不現(xiàn)實(shí)。這里需要一個(gè)關(guān)鍵的觀(guān)察等待只發(fā)生在到達(dá)時(shí)間早于開(kāi)放時(shí)間時(shí)并且等待后進(jìn)入時(shí)間一定是該景點(diǎn)的開(kāi)放時(shí)間a[i]或者某個(gè)更晚的整點(diǎn)。而對(duì)于之后的擴(kuò)展重要的是“從當(dāng)前節(jié)點(diǎn)出發(fā)的時(shí)間”。一個(gè)巧妙且正確的狀態(tài)設(shè)計(jì)是dist[node]表示進(jìn)入節(jié)點(diǎn)node的最早時(shí)間。初始時(shí)dist[1] max(0, a[1])因?yàn)閺臅r(shí)間0在起點(diǎn)開(kāi)始也需要滿(mǎn)足起點(diǎn)開(kāi)放時(shí)間。在BFS過(guò)程中當(dāng)我們從節(jié)點(diǎn)u在時(shí)間dist[u]進(jìn)入嘗試前往鄰居節(jié)點(diǎn)v時(shí)到達(dá)v的時(shí)間是arrive_time dist[u] 1。實(shí)際能進(jìn)入v的時(shí)間是actual_time max(arrive_time, a[v])。如果actual_time dist[v]說(shuō)明我們找到了一條更早進(jìn)入v的路徑那么更新dist[v] actual_time并將節(jié)點(diǎn)v連同新的時(shí)間actual_time重新加入BFS隊(duì)列以待后續(xù)擴(kuò)展。這實(shí)際上是一種帶優(yōu)先級(jí)的BFS或者可以理解為使用隊(duì)列優(yōu)化的Dijkstra算法因?yàn)檫厵?quán)為1所以普通隊(duì)列即可保證時(shí)間單調(diào)不減從而正確性。dist數(shù)組在這里扮演了“最短進(jìn)入時(shí)間”的角色替代了簡(jiǎn)單的“是否訪(fǎng)問(wèn)”標(biāo)記。注意這里有一個(gè)非常重要的細(xì)節(jié)也是初學(xué)者容易出錯(cuò)的地方。為什么能用dist[v]來(lái)記錄并比較因?yàn)閷?duì)于每個(gè)節(jié)點(diǎn)我們只關(guān)心進(jìn)入它的最早時(shí)間。一旦我們找到了一條路徑使得在時(shí)間T進(jìn)入了節(jié)點(diǎn)v那么任何其他在時(shí)間T T才進(jìn)入v的路徑都不可能產(chǎn)生比從時(shí)間T出發(fā)更好的后續(xù)結(jié)果。因此我們可以像Dijkstra算法那樣用dist數(shù)組來(lái)剪枝避免無(wú)效的重復(fù)搜索。3. 算法實(shí)現(xiàn)與細(xì)節(jié)拆解理解了核心思路我們來(lái)具體實(shí)現(xiàn)這個(gè)算法。我將使用C語(yǔ)言進(jìn)行講解因?yàn)檫@是CSP-J/S競(jìng)賽的主流語(yǔ)言。我們會(huì)一步步構(gòu)建代碼并解釋每一個(gè)關(guān)鍵步驟。3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)首先我們需要存儲(chǔ)景點(diǎn)網(wǎng)絡(luò)這是一個(gè)無(wú)向圖題目通常說(shuō)明觀(guān)光巴士線(xiàn)路是雙向的。由于節(jié)點(diǎn)數(shù)N和邊數(shù)M可能達(dá)到10^5級(jí)別我們使用鄰接表來(lái)存儲(chǔ)這是處理稀疏圖的標(biāo)準(zhǔn)且高效的方式。#include iostream #include vector #include queue #include cstring #include algorithm using namespace std; const int MAXN 100005; // 根據(jù)題目數(shù)據(jù)范圍設(shè)定通常1e55 const int INF 0x3f3f3f3f; // 用一個(gè)很大的數(shù)表示“無(wú)窮大”代表尚未到達(dá) int n, m; // n景點(diǎn)數(shù)m巴士線(xiàn)路數(shù) vectorint graph[MAXN]; // 鄰接表存圖 int a[MAXN]; // a[i]表示景點(diǎn)i的開(kāi)放時(shí)間 int dist[MAXN]; // dist[i]表示進(jìn)入景點(diǎn)i的最早時(shí)間dist數(shù)組的初始化至關(guān)重要。起點(diǎn)1的dist[1]不是0而是max(0, a[1])因?yàn)闀r(shí)間0到達(dá)起點(diǎn)時(shí)也需要滿(mǎn)足起點(diǎn)的開(kāi)放時(shí)間。其他點(diǎn)的dist初始化為INF。3.2 BFS隊(duì)列優(yōu)化核心流程我們使用一個(gè)隊(duì)列queue來(lái)進(jìn)行廣度優(yōu)先搜索。但隊(duì)列里存放什么呢我們需要知道當(dāng)前從哪個(gè)節(jié)點(diǎn)、在什么時(shí)間開(kāi)始擴(kuò)展。所以隊(duì)列元素可以就是節(jié)點(diǎn)編號(hào)u因?yàn)閐ist[u]已經(jīng)記錄了進(jìn)入u的最早時(shí)間。void bfs() { // 初始化dist數(shù)組 for (int i 1; i n; i) { dist[i] INF; } dist[1] max(0, a[1]); // 起點(diǎn)進(jìn)入時(shí)間 queueint q; q.push(1); // 從起點(diǎn)開(kāi)始搜索 while (!q.empty()) { int u q.front(); q.pop(); // 當(dāng)前從u節(jié)點(diǎn)出發(fā)的時(shí)間就是dist[u] int current_time dist[u]; // 遍歷u的所有鄰居v for (int v : graph[u]) { // 到達(dá)v的時(shí)間 int arrive_at_v current_time 1; // 實(shí)際能進(jìn)入v的時(shí)間需要滿(mǎn)足開(kāi)放時(shí)間 int enter_v max(arrive_at_v, a[v]); // 如果找到了一條更早進(jìn)入v的路徑 if (enter_v dist[v]) { dist[v] enter_v; q.push(v); // 將v加入隊(duì)列因?yàn)閺膙出發(fā)可能有新的更優(yōu)路徑 } } } }這個(gè)bfs()函數(shù)就是算法的心臟。它保證了每個(gè)節(jié)點(diǎn)v的dist[v]最終存儲(chǔ)的是從起點(diǎn)1出發(fā)在遵守所有景點(diǎn)開(kāi)放時(shí)間規(guī)則下進(jìn)入景點(diǎn)v的最早可能時(shí)間。3.3 完整代碼框架與輸入輸出將以上部分組合起來(lái)并處理好輸入輸出就得到了完整的解決方案。int main() { // 輸入數(shù)據(jù) cin n m; for (int i 1; i n; i) { cin a[i]; } for (int i 0; i m; i) { int u, v; cin u v; // 無(wú)向圖雙向加邊 graph[u].push_back(v); graph[v].push_back(u); } // 執(zhí)行BFS算法 bfs(); // 輸出結(jié)果進(jìn)入終點(diǎn)n的最早時(shí)間。如果dist[n]仍是INF說(shuō)明無(wú)法到達(dá)。 if (dist[n] INF) { cout -1 endl; // 根據(jù)題目要求無(wú)法到達(dá)可能輸出-1或其他 } else { cout dist[n] endl; } return 0; }3.4 時(shí)間與空間復(fù)雜度分析時(shí)間復(fù)雜度本質(zhì)上這是BFS的變種。每個(gè)節(jié)點(diǎn)可能會(huì)被多次加入隊(duì)列每當(dāng)找到一條更早進(jìn)入它的路徑時(shí)。但在最壞情況下每個(gè)節(jié)點(diǎn)被更新的次數(shù)不會(huì)超過(guò)其所有入邊帶來(lái)的不同“進(jìn)入時(shí)間”數(shù)量。由于邊權(quán)為1且時(shí)間只增不減每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)更新dist的次數(shù)可以粗略認(rèn)為是O(1)的更嚴(yán)謹(jǐn)?shù)姆治雠cDijkstra類(lèi)似但隊(duì)列實(shí)現(xiàn)下每個(gè)節(jié)點(diǎn)可能入隊(duì)多次不過(guò)總操作數(shù)與邊數(shù)成線(xiàn)性關(guān)系。因此整體時(shí)間復(fù)雜度可以認(rèn)為是O(N M)這與標(biāo)準(zhǔn)BFS同階完全能夠處理10^5量級(jí)的數(shù)據(jù)?？臻g復(fù)雜度主要用于存儲(chǔ)圖鄰接表O(N M)以及dist數(shù)組和隊(duì)列O(N)總空間復(fù)雜度為O(N M)。實(shí)操心得在競(jìng)賽中遇到這種“帶限制的最短路”首先要想到標(biāo)準(zhǔn)BFS/Dijkstra的局限性然后嘗試定義新的“狀態(tài)”。dist數(shù)組記錄“最早進(jìn)入時(shí)間”是一個(gè)經(jīng)典技巧。另外務(wù)必注意起點(diǎn)的初始化不是0而是max(0, a[1])這個(gè)細(xì)節(jié)一旦忽略整個(gè)算法就錯(cuò)了。4. 思路延伸與算法對(duì)比“旅游巴士”的解法非常優(yōu)雅但它并不是唯一的思考方向。理解不同思路的嘗試與最終解法的關(guān)系能幫助我們更深刻地掌握這類(lèi)問(wèn)題。4.1 錯(cuò)誤思路直接BFS與為什么不行最直觀(guān)的錯(cuò)誤想法就是直接BFS并用一個(gè)vis數(shù)組記錄節(jié)點(diǎn)是否被訪(fǎng)問(wèn)。我們之前已經(jīng)用反例說(shuō)明了問(wèn)題早訪(fǎng)問(wèn)不等于早進(jìn)入。即使我們修改vis的含義記錄“在時(shí)間t訪(fǎng)問(wèn)了節(jié)點(diǎn)v”由于時(shí)間范圍可能很大我們無(wú)法開(kāi)一個(gè)vis[node][time]的二維數(shù)組。而dist數(shù)組的方案巧妙地規(guī)避了這個(gè)問(wèn)題它只記錄每個(gè)節(jié)點(diǎn)迄今為止最好的結(jié)果最早進(jìn)入時(shí)間并用這個(gè)結(jié)果去約束后續(xù)搜索。4.2 另一種視角分層圖思想我們可以把這個(gè)問(wèn)題構(gòu)建成一個(gè)分層圖。什么是分層圖我們把“時(shí)間”也作為一個(gè)維度。創(chuàng)建(node, time)的狀態(tài)對(duì)。從狀態(tài)(u, t)可以轉(zhuǎn)移到狀態(tài)(v, t1)但前提是t1 a[v]否則無(wú)法進(jìn)入v。那么問(wèn)題就轉(zhuǎn)化為在這個(gè)狀態(tài)空間中從(1, max(0, a[1]))到(n, any_time)的最短路目標(biāo)是找到最小的any_time。這個(gè)思路在概念上很清晰但同樣面臨“時(shí)間維度可能很大”的問(wèn)題。不過(guò)它幫助我們理解dist數(shù)組解法的本質(zhì)dist[node]實(shí)際上就是我們?cè)诜謱訄D中到達(dá)node這一層即景點(diǎn)的最早時(shí)間層。我們不需要顯式地存儲(chǔ)所有(node, time)狀態(tài)只需要為每個(gè)node維護(hù)一個(gè)最優(yōu)的time即dist[node]。BFS的過(guò)程就是在不斷地更新這些最優(yōu)時(shí)間層。4.3 與Dijkstra算法的關(guān)聯(lián)如果邊權(quán)不是1而是不同的正整數(shù)那么這個(gè)問(wèn)題就變成了在每個(gè)節(jié)點(diǎn)需要滿(mǎn)足dist[u] a[u]的限制下求起點(diǎn)到終點(diǎn)的最短路。這就不再能用普通隊(duì)列BFS了因?yàn)闀r(shí)間距離不是均勻增加的。此時(shí)我們需要使用**優(yōu)先隊(duì)列小根堆**來(lái)保證每次擴(kuò)展的都是當(dāng)前已知最早時(shí)間的節(jié)點(diǎn)——這就是標(biāo)準(zhǔn)的Dijkstra算法。我們本題的解法可以看作是邊權(quán)為1時(shí)的Dijkstra特例。因?yàn)檫厵?quán)為1所以普通隊(duì)列的FIFO先進(jìn)先出性質(zhì)天然保證了時(shí)間單調(diào)遞增從而起到了優(yōu)先隊(duì)列的作用。這也是為什么我們的算法是正確的。注意事項(xiàng)如果你嘗試用標(biāo)準(zhǔn)Dijkstra優(yōu)先隊(duì)列來(lái)解本題當(dāng)然也是完全正確的而且代碼幾乎一樣只是把queue換成priority_queue排序依據(jù)是dist進(jìn)入時(shí)間。在邊權(quán)為1時(shí)兩者效率接近但普通隊(duì)列常數(shù)更小。理解這種等價(jià)關(guān)系對(duì)于融會(huì)貫通圖論算法很有幫助。5. 常見(jiàn)錯(cuò)誤與調(diào)試技巧即便理解了算法在實(shí)現(xiàn)時(shí)也可能遇到各種問(wèn)題。下面我總結(jié)幾個(gè)常見(jiàn)的“坑點(diǎn)”和調(diào)試方法。5.1 初始化錯(cuò)誤錯(cuò)誤1dist[1] 0。這是最容易犯的錯(cuò)誤。起點(diǎn)在時(shí)間0“出發(fā)”但必須“進(jìn)入”起點(diǎn)才能開(kāi)始旅行。如果a[1] 0比如起點(diǎn)9點(diǎn)才開(kāi)門(mén)那么你實(shí)際能開(kāi)始行動(dòng)的時(shí)間就是9點(diǎn)。所以必須是dist[1] max(0, a[1])。錯(cuò)誤2dist數(shù)組初始化為0。這會(huì)導(dǎo)致后續(xù)比較enter_v dist[v]時(shí)除非找到時(shí)間更早負(fù)數(shù)的路徑否則無(wú)法更新。必須初始化為一個(gè)很大的值如INF。調(diào)試技巧首先單獨(dú)測(cè)試起點(diǎn)初始化?？梢詷?gòu)造一個(gè)簡(jiǎn)單案例n1, m0, a[1]5。正確答案應(yīng)該是5在起點(diǎn)等待到5點(diǎn)。如果你的程序輸出0那就初始化錯(cuò)了。5.2 圖存儲(chǔ)錯(cuò)誤錯(cuò)誤題目明確是無(wú)向圖觀(guān)光巴士線(xiàn)路雙向通行如果只存了單向邊那么很多路徑就斷了導(dǎo)致結(jié)果錯(cuò)誤或無(wú)法到達(dá)。檢查在輸入邊之后可以簡(jiǎn)單打印一下鄰接表看看每個(gè)節(jié)點(diǎn)的鄰居是否對(duì)稱(chēng)對(duì)于無(wú)向圖。5.3 狀態(tài)更新條件理解偏差錯(cuò)誤在判斷是否更新dist[v]時(shí)錯(cuò)誤地使用了arrive_at_v到達(dá)時(shí)間而不是enter_v實(shí)際進(jìn)入時(shí)間進(jìn)行比較。這相當(dāng)于忽略了在節(jié)點(diǎn)v的等待時(shí)間算法就退化成普通BFS必然錯(cuò)誤。錯(cuò)誤在計(jì)算enter_v時(shí)寫(xiě)成了max(arrive_at_v, a[v]) 1多加了1。enter_v已經(jīng)是滿(mǎn)足條件后“進(jìn)入”v的時(shí)間從這個(gè)時(shí)間點(diǎn)就可以開(kāi)始向鄰居擴(kuò)展了再加1就變成了從v出發(fā)的時(shí)間邏輯就亂了。調(diào)試技巧使用一個(gè)小型但能體現(xiàn)“等待”機(jī)制的案例。3 2 0 5 2 1 2 2 3景點(diǎn)開(kāi)放時(shí)間[0, 5, 2]。 路徑1-2-3 和 1-3。從1(0)到2到達(dá)時(shí)間1需等到5enter_25。從1(0)到3到達(dá)時(shí)間1需等到2enter_32。從3(2)到2到達(dá)時(shí)間3仍需等到5enter_25與直接來(lái)一樣。從2(5)到3到達(dá)時(shí)間6a[3]2所以enter_36比之前的2晚不更新。 最終dist[3]2。手動(dòng)模擬這個(gè)過(guò)程與程序輸出對(duì)比。5.4 隊(duì)列使用與重復(fù)入隊(duì)我們的算法允許節(jié)點(diǎn)多次入隊(duì)每當(dāng)找到更早的進(jìn)入時(shí)間時(shí)。這是正確的也是必要的。不要試圖用vis數(shù)組來(lái)阻止節(jié)點(diǎn)第二次入隊(duì)那會(huì)切斷優(yōu)化路徑的可能性。性能擔(dān)憂(yōu)有同學(xué)可能會(huì)擔(dān)心節(jié)點(diǎn)反復(fù)入隊(duì)導(dǎo)致死循環(huán)或超時(shí)。由于dist[v]記錄的是最早進(jìn)入時(shí)間它只會(huì)遞減或不變地更新。對(duì)于整數(shù)時(shí)間每個(gè)節(jié)點(diǎn)v的dist[v]最多被更新a[v]次實(shí)際上遠(yuǎn)少于這個(gè)值。在邊權(quán)為1的圖中這個(gè)更新次數(shù)是有限的不會(huì)造成指數(shù)級(jí)爆炸。5.5 處理無(wú)法到達(dá)的情況題目可能要求如果無(wú)法從起點(diǎn)到達(dá)終點(diǎn)則輸出-1。這通過(guò)檢查最終的dist[n]是否等于初始值INF來(lái)判斷。務(wù)必確保你的INF足夠大大于任何可能的最晚到達(dá)時(shí)間比如可以設(shè)為0x3f3f3f3f這是一個(gè)常用的、相加不會(huì)溢出的較大數(shù)值。6. 實(shí)戰(zhàn)變種與能力提升掌握了“旅游巴士”的基礎(chǔ)解法我們可以看看它的一些變種這能有效提升應(yīng)對(duì)競(jìng)賽題目的能力。6.1 變種一巴士班次有間隔時(shí)間假設(shè)巴士不是隨時(shí)發(fā)車(chē)而是在每條線(xiàn)路上每隔k個(gè)單位時(shí)間才有一班車(chē)?yán)缑?0分鐘一班。那么從節(jié)點(diǎn)u在時(shí)間t出發(fā)到達(dá)節(jié)點(diǎn)v的時(shí)間就不是t1而是大于等于t1且是k的整數(shù)倍的最小時(shí)刻。這相當(dāng)于邊權(quán)變成了動(dòng)態(tài)的wait_time ((t 1) % k 0) ? 0 : (k - (t 1) % k)總耗時(shí)cost 1 wait_time。解法調(diào)整此時(shí)邊權(quán)不再恒為1我們必須使用優(yōu)先隊(duì)列Dijkstra算法。狀態(tài)轉(zhuǎn)移時(shí)計(jì)算next_departure ceil((current_time 1) / k) * k然后到達(dá)時(shí)間arrive_at_v next_departure再與a[v]取大得到enter_v。核心的dist數(shù)組和更新邏輯不變。6.2 變種二多個(gè)巴士同時(shí)出發(fā)求最早全部到達(dá)時(shí)間如果有p輛巴士都從起點(diǎn)1在時(shí)間0出發(fā)它們可以走不同的路徑但共享同樣的規(guī)則景點(diǎn)開(kāi)放時(shí)間、邊通行時(shí)間。目標(biāo)是所有巴士都到達(dá)終點(diǎn)n的最早時(shí)間。這聽(tīng)起來(lái)復(fù)雜但實(shí)際上由于巴士之間不互相影響假設(shè)景點(diǎn)容量無(wú)限問(wèn)題等價(jià)于找一條從1到n的路徑使得最后一輛巴士到達(dá)的時(shí)間最早。因?yàn)槲覀兛梢宰屗邪褪慷甲咄粭l最優(yōu)路徑。所以解法與原題完全一樣求出一輛巴士的最早到達(dá)時(shí)間即可。6.3 變種三輸出具體路徑如果題目不僅要求最早時(shí)間還要求輸出一條滿(mǎn)足該時(shí)間的路徑。我們需要在BFS過(guò)程中記錄“前驅(qū)節(jié)點(diǎn)”。即當(dāng)更新dist[v] enter_v時(shí)同時(shí)記錄pre[v] u表示我們是通過(guò)節(jié)點(diǎn)u在時(shí)間dist[u]進(jìn)入然后到達(dá)并更新了v。算法結(jié)束后從終點(diǎn)n開(kāi)始根據(jù)pre數(shù)組反向回溯到起點(diǎn)1即可得到路徑。注意由于可能存在多條路徑導(dǎo)致相同的dist[n]我們記錄的pre數(shù)組對(duì)應(yīng)的是算法找到的第一條或某一條最優(yōu)路徑。如果需要字典序最小等特定路徑則需要在狀態(tài)更新時(shí)增加比較條件。6.4 如何系統(tǒng)訓(xùn)練此類(lèi)問(wèn)題“旅游巴士”屬于“帶約束的最短路”問(wèn)題。要熟練掌握這類(lèi)問(wèn)題我建議進(jìn)行專(zhuān)題訓(xùn)練鞏固基礎(chǔ)確保標(biāo)準(zhǔn)BFS迷宮問(wèn)題、Dijkstra算法加權(quán)圖最短路非常熟練。理解狀態(tài)設(shè)計(jì)練習(xí)將各種限制條件時(shí)間窗、狀態(tài)依賴(lài)、多點(diǎn)條件轉(zhuǎn)化為圖論模型中的“節(jié)點(diǎn)狀態(tài)”或“邊權(quán)變化”。例如“旅游巴士”將節(jié)點(diǎn)限制轉(zhuǎn)化為狀態(tài)進(jìn)入時(shí)間的一部分。刷題列表可以找一些類(lèi)似的題目進(jìn)行練習(xí)例如“最優(yōu)乘車(chē)”經(jīng)典的公交線(xiàn)路問(wèn)題換乘次數(shù)作為邊權(quán)或狀態(tài)?！半娐肪S修”邊權(quán)有0和1兩種使用雙端隊(duì)列BFS0-1 BFS。“通信線(xiàn)路”求路徑上第k大的邊最小可以使用二分答案最短路判定。模擬與調(diào)試對(duì)于每一道題不要只看AC代碼。嘗試自己構(gòu)建小數(shù)據(jù)手動(dòng)模擬算法過(guò)程并與程序輸出對(duì)比。這是理解算法細(xì)節(jié)、發(fā)現(xiàn)邊界錯(cuò)誤的最有效方法。我個(gè)人在訓(xùn)練學(xué)生時(shí)發(fā)現(xiàn)能把“旅游巴士”這類(lèi)題目的思路講清楚、寫(xiě)正確的同學(xué)其圖論建模能力已經(jīng)達(dá)到了一個(gè)不錯(cuò)的水平。它考察的不僅僅是代碼實(shí)現(xiàn)更是將實(shí)際問(wèn)題抽象為數(shù)學(xué)模型并選用或改造經(jīng)典算法解決問(wèn)題的能力。這正是信息學(xué)競(jìng)賽的核心價(jià)值所在。