P1613 跑路 - histcat

題目#

跑路#

小 A 的工作不僅繁瑣，更有苛刻的規定，要求小 A 每天早上在 $6:00$ 之前到達公司，否則這個月工資清零。可是小 A 偏偏又有賴床的壞毛病。於是為了保住自己的工資，小 A 買了一個空間跑路器，每秒鐘可以跑 $2^k$ 千米（$k$ 是任意自然數）。當然，這個機器是用 longint 存的，所以總跑路長度不能超過 maxlongint 千米。小 A 的家到公司的路可以看做一個有向圖，小 A 家為點 $1$，公司為點 $n$，每條邊長度均為一千米。小 A 想每天能醒得盡量晚，所以讓你幫他算算，他最少需要幾秒才能到公司。數據保證 $1$ 到 $n$ 至少有一條路徑。

$100%$ 的數據滿足 $2\leq n \leq 50$，$m \leq 10 ^ 4$，最優解路徑長度 $\leq$ maxlongint。

題解#

這是一種很奇妙的 dp—— 圖上 dp

然而顯然這並不是 dag，所以考慮新方法

由於跑路機每次只能走 $2^k km$，所以設f[i][u][v]表示是否存在從 u 到 v 的長度為 $2^i$ 的路徑

轉移的話 $2^i$ 可以從 $2^{i-1}$ 轉移來

看代碼吧

問題#

floyd 寫炸了！

代碼#

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

const int N = 55;
int n, m;
bool f[N][N][35];
bool G_new[N][N];
int dis[N][N];


int main()
{
	n = read(), m = read();
	int u, v;
	for(int i = 1;i <= m;i++)
	{
		u = read(), v = read();
		f[u][v][0] = 1;
	}

	for(int k = 1;k <= 33;k++)
	{
		for(int t/*中轉點*/ = 1;t <= n;t++)
			for(int i = 1;i <= n;i++)
			{
				for(int j = 1;j <= n;j++)
				{
					f[i][j][k] |= (f[i][t][k - 1] & f[t][j][k - 1]);
				}
			}
	}
	memset(dis, 0x3f, sizeof dis);

	for(int k = 0;k <= 33;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				G_new[i][j] |= f[i][j][k];
			}
		}
	}

	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			if(G_new[i][j])
				dis[i][j] = 1;
		}
	}

	for(int k = 1;k <= n;k++)
	{
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= n;j++)
			{
				if(k == i || k == j || i == j) continue;
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}

	cout << dis[1][n];
	return 0;
}