今天沒什么好說的那我就賣個萌吧(～￣▽￣)～

Luogu

一道思維題可能僅是對我來說，對于大佬們都是顯然的

---

簡化題意

給你一個圖，找到一個路徑，使其路徑的二進制位中\(1\)的個數最少

分析

這題的題目就有兩個坑點或許僅是對我而言

每次走的時候，只有在端點才可以停下，即如果有一條路從\(i\)到\(j\)，如果其路徑長為7，則不可以從\(i\)直接走到\(j\)，你要走\(3\)次。

由于\(1.\)所以直接跑最短路不一定是最優(yōu)。

然后想解法

首先，由于~~標簽/路徑太長了/牛*的~~機器特殊的跑路方式，所以我們想到了用倍增來解決這個問題

然后考慮這題最后還是要求最短路。我們又看到了數據范圍\(n<=50\)，所以就想到弗洛伊德，求最短路。但由于上面的結論，我們不可以直接跑最短路，故而我們需要對這個圖的做一個轉化。這道題很難對圖的點做出轉化，所以我們選擇對邊/路徑做出轉化。

然后就考慮對路徑的轉化。考慮之前不能直接跑最短路的原因：我們無法在較短的時間里直接確定怎樣的路徑中二進制位的\(1\)的個數更少，所以當我們把路徑的貢獻轉化為它在二進制中\(1\)的個數你就可以算的最短路。

所以先預處理出從\(i\)到\(j\)的最短路徑中\(1\)的個數，然后再求一邊最短路就好的。

對于求\(i\)到\(j\)的最短路徑中\(1\)的個數，由于\(i\)到\(j\)的路徑有一種性質我哦不知道具體的名字：\(i\)到\(t\)中個數為\(k\),\(t\)到\(j\)中個數為\(k\),那么\(i\)到\(j\)中的\(1\)的個數就是\(k+1\)。故，我們可以用類似于傳遞閉包的方式來求的每兩個點之間的最短路中的二進制位的\(1\)的個數

---

code

#include<iostream> #include<cstring> using namespace std; int n,m,x,y,dis[55][55]; bool map[55][55][65]; inline void pre(){for(register int t=0;t<=64;t++)for(register int k=1;k<=n;k++)for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)if(map[i][k][t-1]&&map[k][j][t-1])map[i][j][t]=1,dis[i][j]=1; } inline void floyed(){for(register int k=1;k<=n;k++)for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); } int main(){scanf("%d%d",&n,&m);memset(dis,0x3f,sizeof(dis));for(register int i=1;i<=m;i++)scanf("%d%d",&x,&y),dis[x][y]=1,map[x][y][0]=1;pre();floyed();printf("%d",dis[1][n]); }

---

最后國際慣例，thankyou for your attention

轉載于:https://www.cnblogs.com/fallen-down/p/11589151.html

總結

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

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