P4206 [NOI2005] 聪聪与可可

预处理 nxt[i,j] 表示i到j最近距离i的下一个位置

最后记忆化搜索就好

#include
#include
#include
#include
using namespace std;
int cur,n,m,s,t;
int head[1005],p[1005];
int dis[1005][1005],nxt[1005][1005];
bool vis[1005],visit[1005][1005];
double f[1005][1005];
struct EDGE{
	int t,next;
}e[2005];
#define INF 0x3f3f3f3f

void add(int a,int b)
{
	cur++;
	e[cur].t=b;
	e[cur].next=head[a];
	head[a]=cur;
}

queue < int > q;
void SPFA(int *dis,int *nxt,int s)
{
	dis[s]=0;
	q.push(s);
	while (!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=false;
		for (int h=head[u];h!=-1;h=e[h].next)
		{
			int v=e[h].t;
			if (dis[u]+1