[CSP-S模拟测试]:公园（BFS+剪枝）

题目传送门（内部题31）

输入格式

第一行，五个整数$V,M,N,E,L$。
接下来$M$行，每行两个正整数$s_i,a_i$。保证$s_i$互不相等。
接下来$N$行，每行两个正整数$t_j,b_j$。保证$t_j$互不相等。
接下来$E$行，每行三个正整数$u_k,v_k,w_k$。保证$u_k\neq v_k$，也保证不存在从某一点出发能再次回到该点的路径。

输出格式

一个整数表示$L$时间内最多能访问的景点数，若不存在时间不超过$L$的方案则输出$0$。

样例

样例输入1：

4 1 1 3 17
1 2
4 2
1 2 5
2 3 7
2 4 8

样例输出1：

样例输入2：

2 2 2 1 3
1 1
2 2
1 1
2 2
1 2 3

样例输出2：

数据范围与提示

样例$1$解释：

方案为$1\rightarrow 2\rightarrow 4$，花费时间为$2+5+8+2=17\leqslant 17$。

样例$2$解释：

只能进入景点$1$后立即出来，花费时间为$1+1=2\leqslant 3$。

数据范围：

对于所有数据，$1\leqslant V\leqslant 2,000,1\leqslant E\leqslant 5,000,1\leqslant M,N\leqslant V,1\leqslant s_i,t_j,u_k,v_k\leqslant V,0\leqslant L,a_i,b_j,w_k\leqslant {10}^9$。

题解

当你选择打最基础的暴力的时候你就离$AC$不远了。

当然正解是$DP$，但是我不会……

于是想剪枝，用$dis[i][j]$表示点到$i$，走了$j$个点的最小花费，如果已经不能更新答案，就剪枝。

这就完了……

为方便，将所有的入口连在一个点上，所有的出口连在一个点上。

时间复杂度：$\Theta($玄学$)$。

期望得分：$20$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct node{int id,v,w;}q[5000000];

struct rec{int nxt,to,w;}e[100010];

int head[5010],cnt;

int V,M,N,E,L;

int ans;

int dis[5010][5010],xb[5010][5010];

void add(int x,int y,int w)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	e[cnt].w=w;

	head[x]=cnt;

}

int main()

{

	scanf("%d%d%d%d%d",&V,&M,&N,&E,&L);

	for(int i=1;i<=M;i++)

	{

		int s,a;

		scanf("%d%d",&s,&a);

		add(0,s,a);

	}

	for(int i=1;i<=N;i++)

	{

		int t,b;

		scanf("%d%d",&t,&b);

		add(t,V+1,b);

	}

	for(int i=1;i<=E;i++)

	{

		int u,v,w;

		scanf("%d%d%d",&u,&v,&w);

		add(u,v,w);

	}

	int u=0,v;

	q[v=1]=(node){0,0,0};

	while(u^v)

	{

		node flag=q[++u];

		int x=flag.id,s=flag.v+1,d=flag.w;

		for(int i=head[x],y;i;i=e[i].nxt)

		{

			int qj=dis[y=e[i].to][s];

			if(e[i].w+d>L)continue;

			if(!qj)

			{

				dis[y][s]=e[i].w+d;

				if(y==V+1){ans=max(ans,s);continue;}

				q[xb[y][s]=++v]=(node){y,s,e[i].w+d};

				continue;

			}

			if(e[i].w+d>=qj)continue;

			dis[y][s]=e[i].w+d;

			if(y==V+1){ans=max(ans,s);continue;}

			q[xb[y][s]]=(node){y,s,e[i].w+d};

		}

	}

	printf("%d",ans?ans-1:0);

	return 0;

}

rp++

巴特西