题目（洛谷）
NOIP每年至少一道dp题，然后就考在这道题目上了.
......从这道题开始我就zz了.
看k的数据范围，50以内，嗯，可以做dp.
dp[i][k]表示当前在第i个点，超过i到n的最短距离dis[i]的长度k时的路线条数。
于是方程就很好写了，dp[u][k]+=dp[v][dis[u]+k-dis[v]-w]
初值：dp[1][0]=1。
整个记忆化搜索就行。
然后这个题是个有向图，而且还有环存在，所以我们考虑倒着推过去。
从n开始向1推着走，记录当前状态是否被更新，如果当前状态已访问过再去更新，则说明有0的环存在，输出-1；
注意最后还要来一次dfs(n,k+1)，用以判断0环。
答案就是∑dfs(n,i),0<=i<=k。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define readf(f) scanf(
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
template <class _E> inline void read(_E &e)
{
e=0;bool ck=0;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
if(ck)e=-e;
}
int n,m,k;
ll mod;
struct edge{
int vk;
int wk;
int nxt;
}e[200005],f[200005];
int t=0,t2=0,head[100005],hd2[100005];
inline void ad(int u,int v,int w)
{
e[++t].vk=v;
e[t].wk=w;
e[t].nxt=head[u];
head[u]=t;
f[++t2].vk=u;
f[t2].wk=w;
f[t2].nxt=hd2[v];
hd2[v]=t2;
}
int dis[100005];
bool vis[100005],ac[100005][55];
ll dp[100005][55],ans;
bool no;
inline void data_clear();
inline void sp()
{
queue <int> q;
q.push(1);
dis[1]=0,vis[1]=1;
while (!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
int w=e[i].wk;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
ll dfs(int u,int kk)
{
if (no) return 0;
if (~dp[u][kk]) return dp[u][kk];
ac[u][kk]=1;
dp[u][kk]=0;
for (int i=hd2[u];i;i=f[i].nxt)
{
int v=f[i].vk;
int w=f[i].wk;
int nxk=dis[u]+kk-dis[v]-w;
if (nxk<0) continue;
if (ac[v][nxk])
{
no=true;
return 0;
}
dp[u][kk]+=dfs(v,nxk),dp[u][kk
}
ac[u][kk]=0;
return dp[u][kk];
}
int main()
{
int T;
read(T);
while (T--)
{
data_clear();
read(n),read(m),read(k),read(mod);
for (int i=1;i<=m;++i)
{
int x,y,z;
read(x),read(y),read(z);
ad(x,y,z);
}
sp();
dp[1][0]=1;
for (int p=0;p<=k;++p)
{
ans+=dfs(n,p),an
if (no) break;
}
if (no)
{
puts("-1");
continue;
}
dfs(n,k+1);
if (no)
{
puts("-1");
continue;
}
cout<<ans<<endl;
}
return 0;
}
inline void data_clear()
{
ans=t=t2=0,no=false;
memset(dp,-1,sizeof dp);
memset(vis,0,sizeof vis);
memset(hd2,0,sizeof hd2);
memset(dis,inf,sizeof dis);
memset(ac,0,sizeof ac);
memset(head,0,sizeof head);
}
来说说我是怎么zz的吧。
dp[i][k]我表示的是当前在第i点，超过dis[n]的长度为k的方案数。
GG.
Comments NOTHING