洛谷 P3953 NOIp2017提高组 逛公园 题解【记忆化搜索】【最短路】
点击量：183
我要是考场上会什么最短路……
【问题描述】
策策同学特别喜欢逛公园。 公园可以看成一张N个点M条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，N号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1号点进去，从N号点出来。策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到N号点的最短路长为d，那么策策只会喜欢长度不超过d+K路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？
为避免输出过大，答案对P取模。
如果有无穷多条合法的路线，请输出−1。
【输入格式】
输入文件名为 park.in。
第一行包含一个整数T，代表数据组数。
接下来T组数据，对于每组数据：
第一行包含四个整数N,M,K,P每两个整数之间用一个空格隔开。
接下来M行，每行三个整数$ a_i,b_i,c_i$，代表编号为$ a_i,b_i$的点之间有一条权值为$ c_i$的有向边，每两个整数之间用一个空格隔开。
【输出格式】
输出文件名为 park.out。
输出文件包含T行，每行一个整数代表答案。
【输入输出样例 1】
park.in
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
park.out
3-1
对于第一组数据，最短路为3。
1–5, 1–2–4–5,1–2–3–5为3条合法路径。
【数据规模与约定】
对于不同的测试点， 我们约定各种参数的规模不会超过如下
对于 100%的数据, $ 1\le P \le 10^9,1\le a_i,b_i \le N, 0\le c_i \le 1000$。
数据保证：至少存在一条合法的路线。
前言：
简析一下数据梯度。
10分：floyd求最短路计数。
30分：spfa求最短路计数。
70分：不用判0环（输出-1）的正解。
100分：正解/没有判过1的0环（样例2没过）$ \Rightarrow $
。
题解：
可以用记忆化搜索过掉，首先SPFA预处理出从1出发的单源最短路径，接着判断有无过1的0环(出于严谨，虽然没有必要)，有则输出-1。考虑类似背包的转移，也就是对于点$ v,d[v]+x,x\in [0,k]$，设存在边$ (u,v)=w$，则可以由$ t=x-[w-(dis[v]-dis[u])]$转移。当w在最短路上时，就是由同层的$ x$转移，如果不在最短路上，就是由不同层的$ t$转移。当$ t\le 0$时，不合法，就不转移。
因为我们的状态是由前面（靠近源点）状态转移过来的，所以记忆化搜索是倒着做的。在做完SPFA后，将图的方向反过来，就是dfs时用的图。那么一个点如果被搜索过，可以直接调用它的状态；如果一个点没有搜索过，就继续搜索它；如果它还在系统栈里，说明找到了环，此时判断上述$ t$是否合法，如果不合法则递归，如果合法就当它没有搜索过。如果出现0环，则两次找到某个点时，利用的$ x$是相同的，此时判断找到0环，输出-1。
同时，记忆化搜索是要做$ k$遍的，因为做第i次时，只有f[u][1…i]是全部有效/合法的。所以做k次保证了所有转移来的都是合法的，不合法的初始值f[i][j]=-1，f[1][0]=1，存的是方案数。
Code：
#include<cstdio>
#include<cstring>
#include<queue>
using std::deque;
struct edge
{
int n,v,nxt;
edge(int n,int v,int nxt)
{
this->n=n;
this->v=v;
this->nxt=nxt;
}
edge()
{
nxt=-1;
}
}e[210000],E[210000];
int head[101000],Head[101000],Ecnt=-1,ecnt=-1;
void add(int from,int to,int v)
{
e[++ecnt]=edge(to,v,head[from]);
head[from]=ecnt;
}
void Add(int from,int to,int v)
{
E[++Ecnt]=edge(to,v,Head[from]);
Head[from]=Ecnt;
}
int p;
int f[101000][55];
bool in[101000];
int dis[101000];
void spfa()
{
memset(dis,0x3f,sizeof(dis));
in[1]=true;
dis[1]=0;
deque<int> q;
q.push_back(1);
while(!q.empty())
{
int k=q.front();
q.pop_front();
in[k]=false;
for(int i=Head[k];~i;i=E[i].nxt)
{
if(dis[E[i].n]>dis[k]+E[i].v)
{
dis[E[i].n]=dis[k]+E[i].v;
if(!in[E[i].n])
{
in[E[i].n]=true;
if(q.empty()||dis[E[i].n]<dis[q.front()])
q.push_front(E[i].n);
else
q.push_back(E[i].n);
}
}
}
}
}
bool used[101000][51];
int flag=0;
int dfs(int x,int k)
{
int t;
if(f[x][k]==-1)
f[x][k]++;
for(int i=head[x];~i;i=e[i].nxt)
{
int tmp=0;
t=k-(e[i].v-(dis[x]-dis[e[i].n]));
if(t<0)
continue;
if(!used[e[i].n][t]&&~f[e[i].n][t])
f[x][k]+=f[e[i].n][t];
else
{
if(used[e[i].n][t])
{
flag=1;
return 0;
}
used[e[i].n][t]=true;
f[x][k]+=dfs(e[i].n,t);
if(!tmp)
used[e[i].n][t]=false;
if(flag)
return 0;
}
f[x][k]%=p;
}
return f[x][k];
}
bool Used[101000];
int nega;
void Dfs(int x)//判过1的0环
{
for(int i=Head[x];~i;i=E[i].nxt)
if(E[i].v==0)
{
if(Used[E[i].n])
{
nega=1;
return;
}
Used[E[i].n]=true;
Dfs(E[i].n);
}
}
int main()
{
int T,n,m,k;
int u,v,w;
scanf("%d",&T);
while(T--)
{
memset(Used,0,sizeof(Used));
memset(used,0,sizeof(used));
memset(in,0,sizeof(in));
memset(f,-1,sizeof(f));
scanf("%d%d%d%d",&n,&m,&k,&p);
memset(head,-1,sizeof(head));
memset(Head,-1,sizeof(Head));
ecnt=-1;
Ecnt=-1;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&u,&v,&w);
Add(u,v,w);
add(v,u,w);
}
spfa();
Used[1]=true;
nega=0;
Dfs(1);
if(nega)
{
puts("-1");
continue;
}
f[1][0]=1;
int ans=0;
for(int i=0;i<=k;++i)
{
memset(used,0,sizeof(used));
used[n][i]=true;
flag=0;
f[n][i]=dfs(n,i)%p;
ans+=f[n][i];//答案是全部d+x x∈[0,k]的所有合法方案
ans%=p;
if(flag)
{
ans=-1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}
说点什么