ｓｐｆａ＋ｄｐ＋反向ｓｐｆａ　洛谷　 P3953 逛公园

本文主要是介绍ｓｐｆａ＋ｄｐ＋反向ｓｐｆａ　洛谷　 P3953 逛公园，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

策策同学特别喜欢逛公园。公园可以看成一张 NN 个点 MM 条边构成的有向图，且没有自环和重边。其中1号点是公园的入口， NN 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从 NN 号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到 NN 号点的最短路长为 dd ，那么策策只会喜欢长度不超过 d+ Kd+K 的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对 PP 取模。

如果有无穷多条合法的路线，请输出−1。

输入输出格式

输入格式：

第一行包含一个整数 TT , 代表数据组数。

接下来 TT 组数据，对于每组数据：第一行包含四个整数 N,M,K,PN,M,K,P ，每两个整数之间用一个空格隔开。

接下来 MM 行，每行三个整数 a_i,b_i,c_iai​,bi​,ci​ ，代表编号为 a_i,b_iai​,bi​ 的点之间有一条权值为 c_ici​ 的有向边，每两个整数之间用一个空格隔开。

输出格式：

输出文件包含 TT 行，每行一个整数代表答案。

输入输出样例

输入样例#1： 复制

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

输出样例#1： 复制

3

-1

说明

【样例解释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 10001≤P≤109,1≤ai​,bi​≤N,0≤ci​≤1000 。

数据保证：至少存在一条合法的路线。

算法分析：

首先用spfa求出最短路，d[i]表示i点到起点的最短距离Dis[i]功能就可以告诉我们当前所走的路是否有“冤枉路”了。解释：“冤枉路”是指从A点至B点所走的路径不是最短路，也就是说一共允许你走K冤枉路的长度，每走一次冤枉路都会消耗这个余额。Dp求解dp(i,j)就表示你当前在i点，还允许你走j容量的“冤枉路”。

那无穷多条合法路线：首先肯定是在路径里出现了环。（解释：因为简单路线肯定是有限条，无穷的肯定是有环）题目里提到了0边，这就使我们进一步想到0环——如果这个环不是零环，那肯定就不是在最短路上面了（何必绕着一点跑到黑呢！）肯定就会消耗“冤枉路”容量，就不可能是有限条。所以如果有0环出现，判断-1即可。

注意事项

虽然1号点一定能走到n号点，但是公园中有些点可能无法到达N，所以通过建立反向图的方式反向SPFA来排除那些无法到终点的点，把能到终点的点vis[i]值标为1即可，在dp的时候把vis值为0的点跳过即可

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7ffffff;
struct node
{int x;int w;node(int x1,int w1):x(x1),w(w1){}
};
int n,m,k,p;
#define N 100007
vector<node>g1[N];
vector<node>g2[N];
int dis[N];
int ans[N][55];
bool vis[N],flag[N][55];
bool a[N];
int dfs(int a,int b)//a代表现在所在的点，b的容量
{if(b<0) {return 0;}else if(flag[a][b]==1){return -INF;}else if(ans[a][b]!=-1)return ans[a][b];else{flag[a][b]=1;int key=0;if(a==n){key++;}for(int i=0;i<g1[a].size();i++){int g=g1[a][i].x;int y=g1[a][i].w;int u=dis[g]-dis[a];if(vis[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;flag[a][b]=0;return key;}
}
int fspfa(int s)  //建立反向图，用vis记录终点是否可以到起点
{memset(vis,0,sizeof(vis));queue<int>q;q.push(s);vis[s]=1;while(!q.empty()){int i=q.front();q.pop();for(int j=0;j<g2[i].size();j++){int k=g2[i][j].x;if(!vis[k]){vis[k]=1;q.push(k);}}}
}
int spfa(int s)
{for(int i=2;i<=n;i++)dis[i]=INF;memset(vis,0,sizeof(vis));queue<int>q;q.push(s);dis[s]=0;vis[s]=1;while(!q.empty()){int i=q.front();q.pop();vis[i]=0;for(int j=0;j<g1[i].size();j++){int k=g1[i][j].x;int w=g1[i][j].w;if(dis[k]>dis[i]+w){dis[k]=dis[i]+w;if(!vis[k]){vis[k]=1;q.push(k);}}}}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d%d%d",&n,&m,&k,&p);for(int i=1;i<=n;i++){g1[i].clear();g2[i].clear();for(int j=0;j<=k;j++){ans[i][j]=-1;flag[i][j]=0;}}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g1[a].push_back(node(b,c));g2[b].push_back(node(a,c));}spfa(1);fspfa(n);int z=dfs(1,k);if(z==-INF){printf("%d\n",-1);}else{printf("%d\n",z);}}return 0;
}

这篇关于ｓｐｆａ＋ｄｐ＋反向ｓｐｆａ　洛谷　 P3953 逛公园的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！