1. 首頁 > 生活百科 > >

Autobus 方法記錄

生活百科Autobus 方法記錄

原題鏈接
[COCI2021-2022#4] Autobus題目描述在一個國家里有 \(n\) 座城市 。這些城市由 \(m\) 條公交線路連接，其中第 \(i\) 條線路從城市 \(a_i\) 出發，到 \(b_i\) 停止，路程中耗時 \(t_i\) 分鐘 。
Ema 喜歡旅行，但她并不喜歡在公交線路之間換乘 。在旅行過程中，她希望最多只需坐 \(k\) 個不同的公交線路 。
Ema 想知道 ， 從城市 \(c_i\) 到城市 \(d_i\) 的最短旅行時間是多少（最多坐 \(k\) 個不同的公交線路） 。
輸入格式第一行包含兩個整數 \(n,m\)，分別表示城市的數量和公交車線路的數量 。
接下來 \(m\) 行，第 \(i+1\) 包含三個整數 \(a_i,b_i,t_i\)，分別表示第 \(i\) 條公交車線路的起點、終點和從起點到終點所需的時間 。
接下來一行包含兩個整數 \(k,q\)，最大坐的不同公交線路的個數和問題題的個數 。
接下來 \(q\) 行，第 \(m+j+3\) 行包含兩個整數 \(c_j,d_j\)，表示詢問從城市 \(c_j\) 到城市 \(d_j\) 的最短旅行時間 。
輸出格式輸出包含 \(q\) 行，第 \(i\) 行包含一個整數，表示從城市 \(c_i\) 到城市 \(d_i\) 的最短旅行時間 。
樣例 #1樣例輸入 #14 71 2 11 4 102 3 12 4 53 2 23 4 14 3 21 31 44 23 3樣例輸出 #110-10樣例 #2樣例輸入 #24 71 2 11 4 102 3 12 4 53 2 23 4 14 3 22 31 44 23 3樣例輸出 #2640樣例 #3樣例輸入 #34 71 2 11 4 102 3 12 4 53 2 23 4 14 3 23 31 44 23 3樣例輸出 #3340提示【樣例解釋】

Autobus 方法記錄

文章插圖
每個樣例中的答案都已經標記在圖中 。
【數據規模與約定】
本題采用子任務捆綁測試 。
  • Subtask 1（15 pts）：\(k ≤ n ≤ 7\) 。
  • Subtask 2（15 pts）：\(k ≤ 3\) 。
  • Subtask 3（25 pts）：\(k ≤ n\) 。
  • Subtask 4（15 pts）：沒有額外限制 。
對于 \(100\%\) 的數據，\(2\le n \le 70,1\le m,t_i\le 10^6,1\le a_i,b_i,c_j,d_j\le n,1\le k\le10^9,1\le q \le n^2\) 。
【提示與說明】
本題分值按 COCI 原題設置，滿分 \(70\) 。
題目譯自 COCI2021-2022 CONTEST #4 T2Autobus 。
題解題目的要求是求全源最短路，而且\(n\)（圖上總點數）非常小，和\(floyd\)的相性很好，所以首先考慮\(floyd\)算法 。
本題的第一個難點在于“最多只需坐\(k\)個不同的公交線路” 。但仔細觀察數據范圍，\(2\le n \le 70,1\le k \le10^9\) ， 可以見得在大部分情況下，\(k\)是比\(n\)大的 。因為每個點至多到一次，所以一個點到該定點的線路也最多走一次，最復雜的旅行方案也只需要走\((n-1)\)條線路 。而\(k\)比\(n\)大就意味著旅行不再受“最多只需坐\(k\)個不同的公交線路”的限制 。
所以，對于這部分的數據，我們可以跑一個裸的\(floyed\)來處理出圖上任意兩個點之間的最短路 。
if(k>=n){ for(int l=1;l<=n;l++)//l枚舉斷點 {for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)//floyd標志性的三層for循環{ans[i][j]=minn(ans[i][j],ans[i][l]+ans[l][j]);//ans[i][j]根據floyd算法的定義，為i到j的最短路}} }}那么剩下的問題就是處理會受\(k\)值限制的情況了 。
既然有一個對經過路徑條數限制的條件，那么我們不妨給記錄最短路的數組再增加一個維度 。
令\(dis[i][j][k]\)表示經過\(k\)條邊的前提下，\(i\)到\(j\)的最短路 。再加入\(k\)限制之前，我們先來看看傳統的\(floyd\)是如何工作的 。
Autobus 方法記錄

文章插圖
可以直觀地看到，類似動態規劃，\(dis[i][j]\)可能由\(dis[i][l]+dis[l][j]\)更新而來，或者由\(dis[i][j]\)直接繼承 。
那么考慮在這個更新的過程中加入\(k\)的限制 。
若\(dis[i][j]\)是由\(dis[i][l]+dis[l][j]\)更新而來的，那么在這種情況下\(i\)到\(j\)的經過邊數就是\(i\)到\(l\)的經過邊數與\(l\)到\(j\)的經過邊數的總和 。
Autobus 方法記錄

文章插圖
那\(i\)到\(j\)可能的經過的邊數就可以通過\(i\)到\(l\)與\(l\)到\(j\)可能經過的邊數更新 。我們的方法是 ， 外層循環從\(1\)到\(k\)枚舉\(i\)到\(l\)可能經過的邊數\(p1\) ， 內層循環從\(1\)枚舉\(l\)到\(j\)可能經過的邊數\(p2\)，且\(p1+p2<=k\).
Autobus 方法記錄

文章插圖
k=minn(k,n);for(int l=1;l<=n;l++)//l枚舉斷點{ for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++)//floyd標志性的三層for循環{for(int p1=1;p1<=k;p1++)//i到l可能的邊數{for(int p2=1;p2<=k&&p1+p2<=k;p2++)//l到j可能的邊數{dis[i][j][p1+p2]=minn(dis[i][j][p1+p2],dis[i][l][p1]+dis[l][j][p2]);}}} }}

推薦閱讀