洛谷p1613 跑路

大緻題意：給一張有向圖(存在自環)，每條邊權均為1，現在有一人要從1号結點走到n号結點，但是這個人有一個神奇的瞬移機器，這個機器走 2 k 2^k 2k( k k k為自然數)花費的時間都為1，問從起點到終點的最小花費時間。

思路如下：

step 1.我們可以處理出所有的從一個點到達另一個點的距離可以為 2 k 2^k 2k的路徑，并把這兩個點之間連一條權值為1的邊。

step 2.在我們新得到的圖上運作最短路算法，求出從起點到達終點花費的最少時間。

下面我們來看看如何處理step 1:

狀态表示：用 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]記錄能否通過 2 k 2^k 2k的距離從 i i i到達 j j j.

轉移方程： i f ( f [ i ] [ u ] [ k − 1 ] if(f[i][u][k-1] if(f[i][u][k−1]&& f [ u ] [ j ] [ k − 1 ] ) f[u][j][k-1]) f[u][j][k−1]) 則 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]為真。

需要注意：因為題意已經給出任意邊的邊權均為1，則可以用反證法證明：若 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]為真，則一定存在中間結點使得 f [ i ] [ u ] [ k − 1 ] f[i][u][k-1] f[i][u][k−1]&& f [ u ] [ j ] [ k − 1 ] f[u][j][k-1] f[u][j][k−1]為真。

代碼如下：

#include<cstring>
#include<iostream>
using namespace std;
const int N = 100, M = 20000;
const int K = 35;
int f[N][N][K];
int g[N][N];
int n,m;
int main()
{
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int a,b;
		cin>>a>>b;
		f[a][b][0]=1;
		g[a][b]=1;
	}
	for(int u=1;u<=32;++u)
		for(int k=1;k<=n;++k)
			for(int i=1;i<=n;++i)
				for(int j=1;j<=n;++j)
					if(f[i][k][u-1]==1&&f[k][j][u-1]==1)
					{
						f[i][j][u]=1;
						g[i][j]=1;
					}

	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
	
	cout<<g[1][n]<<endl;
	return 0;
}