2017 noip Day1 T2 逛公园

（洛谷P3953）传送门

输出输入数据自己找

这个题看到其他的大佬有用dp做的。
推荐一个大佬的讲解
本蒟蒻dp学得烂，东拼拼西凑凑勉强懂了。就发一个dfs+spfa最短路的方法做的吧。

本题就先建图，注意是双向边反着跑spfa，因为是有向图所以反着跑会省略掉很多无法从起点通往n的点（你自己在草稿本上画个图就知道啦）。跑一边spfa后找到所有dis值，用f[i][j]表示从n到i的距离<最短距离+k的方案数，对于每一条边都尝试走，而这个状态可以表示为u->v: d[u]-d[v]+k-len[u->v];最后西格玛求和就好。

核心代码如下：

for(i=head1[v];~i;i=e1[i].nex)
	{
		u=e1[i].v;w=e1[i].w;
		x=dis[v]+k-w-dis[u];//这个表达式，表示用尝试当前这条边替换其中最短路径里的一条边
		if(x<0||x>k) continue;//这种情况不合法，跳过
		dp[v][k]=(dp[v][k]+dfs(u,x))%p;
		if(flag==0) return 0;
	}

附上完整代码

/***********************
*    Problem:P3953 逛公园   *
*    User: mzg1824_TY *
*    Language: C++     *
*    Date：2018.1.23   *
*    algorithm：深度优先搜索+spfa 	*
**********************/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+5;

struct node
{
	int v,w,nex;
}e[maxn*2],e1[maxn*2];

int n,m,k,d,p;
int cnt=0,head[maxn],head1[maxn],dis[maxn],di[maxn],tt[maxn];
int l,r,q[maxn*4],dp[maxn][55],ans;
bool vis[maxn],flag;
int vv[maxn][55];

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=10*x+ch-'0';ch=getchar();}
	return x*f;
}

void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt;
}

void add1(int u,int v,int w)
{
	e1[++cnt].v=v;
	e1[cnt].w=w;
	e1[cnt].nex=head1[u];
	head1[u]=cnt;
}

void init()
{
	freopen("input.txt","r",stdin);
}

void spfa(int s)
{
	int i,u,v;
	l=1;r=1;q[1]=s;
	memset(dis,12,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[s]=0;vis[s]=true;//vis染色标记
	while(l<=r)
	{
		u=q[l];l++;
		vis[u]=false;
		for(i=head[u];i!=-1;i=e[i].nex)
		{
			v=e[i].v;
			if(dis[u]+e[i].w<dis[v])
			{
				dis[v]=dis[u]+e[i].w;//找最短路径
				if(!vis[v])
				{
					r++;q[r]=v;
					vis[v]=true;
				}
			}
		}
	}
}

int dfs(int v,int k)
{
	if(vv[v][k]==1||flag==0)//如果存在负环或者这个路径已经走过了，重复走则是无穷解
	{
		flag=0;
		return 0;
	}
	if(vv[v][k]==2) return dp[v][k];//vv[v][k]表示dp数组已经有值了，直接返回
	int i,u,w,x;
	vv[v][k]=1;//打上标记，防止负环出现，有负环直接跳
	for(i=head1[v];~i;i=e1[i].nex)
	{
		u=e1[i].v;w=e1[i].w;
		x=dis[v]+k-w-dis[u];
		if(x<0||x>k) continue;
		dp[v][k]=(dp[v][k]+dfs(u,x))%p;
		if(flag==0) return 0;//判断这条路走没有
	}
	vv[v][k]=2;//打上标记，dp数组已有值，再次出现就直接跳
	return dp[v][k];
}

void readdata()
{
	int i,u,v,w,T;
	T=read();
	while(T--)
	{
		n=read();
		m=read();
		k=read();
		p=read();
		memset(head,-1,sizeof(head));
		memset(head1,-1,sizeof(head1));//注意赋值，不赋值就等着wa吧
		for(i=1;i<=m;i++)
		{
			u=read();
			v=read();
			w=read();
			add(u,v,w);//建图
			add1(v,u,w);
		}
		spfa(1);
		memset(dp,0,sizeof(dp));
		memset(vv,0,sizeof(vv));
		dp[1][0]=1;
		ans=0;flag=1;//先给flag附个值后面可以打标记
		for(i=0;i<=k;i++) ans=(ans+dfs(n,i))%p;
		if(flag==0) printf("-1\n");
		else printf("%d\n",ans);
	}
}

void work()
{
}

int main()
{
	init();//本人喜欢文件读入，可以随个人爱好，若不喜欢注释即可
	readdata();
	work();
	return 0;
}