P4159 [SCOI2009] 迷路

題意：

該有向圖有 n 個節點，節點從 1 至 nn 編號，windy 從節點 1 出發，他必須恰好在 t 時刻到達節點 n。

現在給出該有向圖(帶邊權)，你能告訴 windy 總共有多少種不同的路徑嗎？

答案對 2009 取模。

題解：

如果邊權只有0和1，那么就是矩陣快速冪的板子題，可惜不是，現在邊權大于1，就不是存板子，但是邊權也小于10，那也就是我們可以把這個1個點拆開看，最多也就拆成9個而已。
我們令序數對(i，j)，i屬于[1,n],j∈[0,8],表示點i拆成的第j個點，其中第0個點是真點，其余是假點
我們令(i,j)(j屬于[1,8])表示到真點(i,0)的距離為j的假點，只要讓(i,j)向(i,j-1)連一條邊權為1的邊
而對于原圖中一條從u到v的邊權為w的邊，我們只要讓(u,0)向(v,w-1)連一條邊權為1的邊
有點像分層圖的感覺，就是把邊權給分解開了

這樣就還原了一開始那種只有01的邊，此時矩陣變成9n * 9n的矩陣，直接跑矩陣快速冪就行

代碼：

總結

以上是生活随笔為你收集整理的P4159 [SCOI2009] 迷路的全部內容，希望文章能夠幫你解決所遇到的問題。

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