题解P3953 逛公园
一些思路
这道题运用的思想和最短路计数的思想差不多，但是题目当中还允许不超过最短路长度K的路径，那么就需要在最短路计数上稍作变通才可以：
- 当然和最短路计数的套路一样，我们需要知道最短路到底是多少才可以判断某条路径是否满足要求，就先用SPFA算法来求一下最短路。
- 知道最短路之后我们怎么求解满足路径的条数呢？假想一下我们现在从起点开始走——由于我们已经使用SPFA大法来完成了求最短路的使命，我们自然而然的就维护出来了一个d数组（d[i]表示i点到起点的最短距离）这种功能就可以告诉我们当前所走的路是否有“冤枉路”了。解释：“冤枉路”是指从A点至B点所走的路径不是最短路，也就是说一共允许你走K冤枉路的长度，每走一次冤枉路都会消耗这个余额。
- 通过想象这个过程就能知道前面你的选择会对后面有影响，很自然的想到dp求解，dp(i,j)就表示你当前在i点，还允许你走j容量的“冤枉路”。
- 那什么时候有无穷多条合法路线呢？首先肯定是在路径里出现了环。（解释：因为简单路线肯定是有限条，无穷的肯定是有环）题目里提到了0边，这就使我们进一步想到0环——如果这个环不是零环，那肯定就不是在最短路上面了（何必绕着一点跑到黑呢！）肯定就会消耗“冤枉路”容量，就不可能是有限条。所以如果有0环出现，判断-1即可。
一些注意事项
- 虽然1号点一定能走到n号点，但是公园中有些点可能无法到达N，所以通过建立反向图的方式反向SPFA来排除那些无法到终点的点，把能到终点的点alive[i]值标为1即可，在dp的时候把alive值为0的点跳过即可
- 本题有多组数据，请大家一定要记得清空数组！
一些代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x7FFFFFFF;
struct node
{
int x;
int y;
node(int x1,int y1):x(x1),y(y1){}
};
int n,m,k,p;
vector<node>v[100007];
vector<node>s[100007];
int d[100007];
int ans[100007][57];
bool vis[100007][57];
bool alive[100007];
queue<int>q;
queue<int>f;
int dfs(int a,int b)
{
if(b<0)
{
return 0;
}
else if(vis[a][b]==1)
{
return -INF;
}
else if(ans[a][b]!=-1)
{
return ans[a][b];
}
else
{
vis[a][b]=1;
int key=0;
if(a==n)
{
key++;
}
for(int i=0;i<v[a].size();i++)
{
int g=v[a][i].x;
int y=v[a][i].y;
int u=d[g]-d[a];
if(alive[g]==0)
{
continue;
}
int w=dfs(g,b-(y-u));
if(w==-INF)
{
return -INF;
}
else
{
key=(key+w)%p;
}
}
ans[a][b]=key%p;
vis[a][b]=0;
return key;
}
}
void safe()
{
f.push(n);
alive[n]=1;
while(!f.empty())
{
int h=f.front();
f.pop();
for(int i=0;i<s[h].size();i++)
{
int g=s[h][i].x;
if(alive[g]==0)
{
alive[g]=1;
f.push(g);
}
}
}
return;
}
void spfa()
{
q.push(1);
d[1]=0;
while(!q.empty())
{
int h=q.front();
q.pop();
for(int i=0;i<v[h].size();i++)
{
int g=v[h][i].x;
int y=v[h][i].y;
if(d[h]+y<d[g])
{
d[g]=d[h]+y;
q.push(g);
}
}
}
return;
}
int main(){
int t=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1;i<=n;i++)
{
v[i].clear();
alive[i]=0;
for(int l=0;l<=k;l++)
{
ans[i][l]=-1;
vis[i][l]=0;
}
}
for(int i=0;i<m;i++)
{
int a=0,b=0,c=0;
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(node(b,c));
s[b].push_back(node(a,c));
}
for(int i=2;i<=n;i++)
{
d[i]=INF;
}
spfa();
safe();
int z=dfs(1,k);
if(z==-INF)
{
printf("%d\n",-1);
}
else
{
printf("%d\n",z);
}
}
return 0;
}