?

洛谷P1119 災后重建

圖論 ? 腦洞題 ? floyd ??
floyd中 k 的意義 通過前 k 個點 作為中間的節點 更新 i 到 j 的最短路 也就是 只經過前 k 個點 的最短路

幫助理解Floyd算法的好題！初學Floyd算法時，相信很多人和我一樣，只是把幾行代碼背下來，
并沒有了解Floyd算法到底是什么原理。以下介紹Floyd算法的原理：

Floyd算法的本質是動態規劃，其轉移方程為：f(k,i,j) = min( f(k-1,i,j), f(k-1,i,k)+f(k-1,k,j) )。

f(k,i,j)表示路徑除開起點i與終點j，只經過前k個點中的某些點，從i到j的最小值。計算這個值只需要考慮兩種情況：
最短路經過k，和最短路不經過k（那么就經過前k-1個點中的某些點）。由于k要從k-1轉移而來，自然k為最外層的循環。
而經過狀態壓縮（類似于背包問題）后，就變成了我們熟悉的f(i,j) = min( f(i,j), f(i,k)+f(k,j) )了。

本題同理，只是k表示的是最先修好的前k個村莊。不過由于出題人非常良心地幫我們把修理時間和詢問時間都排序了，
所以就沒什么關系了- -用Floyd枚舉k時，枚舉到下一個詢問的時間點就停止。回答詢問之后，再繼續枚舉。

?

1 #include <cstdio> 2 #include <cmath> 3 #include <cstdlib> 4 #include <cstring> 5 #include <string> 6 #include <iostream> 7 #include <iomanip> 8 using namespace std ; 9 10 const int maxn = 211,maxq = 50011,inf = 1e9 ; 11 int n,m,Q,now ; 12 int e[maxn][maxn],t[maxn] ; 13 int tq[maxq],qs[maxq],qt[maxq] ; 14 15 inline int read() 16 { 17 char ch = getchar() ; 18 int x = 0 , f = 1 ; 19 while(ch<'0'||ch>'9') { if( ch=='-' ) f = -1 ; ch = getchar() ; } 20 while(ch>='0'&&ch<='9') { x = x*10 + ch - 48 ; ch = getchar() ; } 21 return x * f ; 22 } 23 24 inline int print(int now) 25 { 26 if( t[ qs[now] ] > tq[ now ] || t[ qt[now] ] > tq[ now ] ) 27 return -1 ; 28 if( e[qs[now]][qt[now]]==inf ) 29 return -1 ; 30 return e[qs[now]][qt[now]] ; 31 } 32 33 int main() 34 { 35 n = read() ; m = read() ; 36 for(int i=0;i<n;i++) t[ i ] = read() ; 37 for(int i=0;i<n;i++) 38 for(int j=0;j<n;j++) e[ i ][ j ] = inf ; 39 40 41 int x,y,v ; 42 for(int i=1;i<=m;i++) 43 { 44 x = read() ; y = read() ; v = read() ; 45 e[ x ][ y ] = v ; e[ y ][ x ] = v ; 46 } 47 48 Q = read() ; 49 for(int i=1;i<=Q;i++) 50 { 51 qs[ i ] = read() ; qt[ i ] = read() ; tq[ i ] = read() ; 52 } 53 54 now = 1 ; 55 for(int k=0;k<n;k++) 56 { 57 while( now <= Q && tq[now] < t[ k ] ) // 這樣相當于做詢問 Q 是 就已經將 在他之前的 邊考慮到 58 //詢問的時間小于當前時間則輸出 59 { 60 printf("%d\n",print( now ) ) ; 61 now++ ; 62 } 63 for(int i=0;i<n;i++) 64 for(int j=0;j<n;j++) 65 e[ i ][ j ] = min(e[ i ][ j ],e[ i ][ k ] + e[ k ][ j ]) ; 66 } 67 68 while( now<=Q ) 69 { 70 printf("%d\n",print(now)) ; 71 now++ ; 72 } 73 74 return 0 ; 75 }

?

轉載于:https://www.cnblogs.com/third2333/p/7097440.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的洛谷P1119 灾后重建 图论 脑洞题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。