histcat

Problem#

Running Away#

Little A's job is not only tedious but also has strict regulations, requiring Little A to arrive at the company before $6:00$ every morning, otherwise his salary for the month will be zeroed. However, Little A has a bad habit of oversleeping. To keep his salary, Little A bought a space running machine that can run $2^k$ kilometers per second (where $k$ is any natural number). Of course, this machine is stored using longint, so the total running distance cannot exceed maxlongint kilometers. The road from Little A's home to the company can be viewed as a directed graph, with Little A's home as point $1$ and the company as point $n$, and each edge has a length of one kilometer. Little A wants to wake up as late as possible every day, so he asks you to help him calculate the minimum number of seconds he needs to reach the company. The data guarantees that there is at least one path from $1$ to $n$.

$100%$ of the data satisfies $2\leq n \leq 50$, $m \leq 10 ^ 4$, and the optimal path length $\leq$ maxlongint.

Solution#

This is a very interesting dp—dp on graphs.

However, it is clear that this is not a DAG, so consider a new method.

Since the running machine can only travel $2^k km$ at a time, let f[i][u][v] represent whether there exists a path from $u$ to $v$ of length $2^i$.

The transition can be made from $2^{i-1}$.

Check the code.

Problem#

Floyd's algorithm is broken!

Code#

#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/*intermediate point*/ = 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;
}