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;
}