这道题看了第三遍了, 还是想不出来.
写篇记录增强一下印象吧.
题意
有一张 \(n\) 个点, \(m\) 条边的有向图 \((n\le 10^5, m \le 2*10^5)\), 没有自环和重边,
每一条边都有一个非负权值,
设 \(d\) 为节点 \(1\) 到节点 \(n\) 的最短路, 求 \(1\) 到 \(n\) 的路径中长度不超过 \(d+k\) 的路径数量 \((k \le 50)\).
思路
第一次看这道题是大概一年前了, 完全没有思路, 抄了篇题解走人.
第二次稍微有点思路, 但是跑偏了, 总向着 \(SPFA\) 那个方向来统计数量, 并且也不太懂怎么判 \(0\) 环, 最后还是看了自己第一次的代码.
这一次又看了这道题, 思路还是和第二次差不多, 实在觉得不行, 还是要写一篇解题记录.
这次又看了一遍, 才发现这题实际上是一道搜索题, 设状态, 然后记忆化搜索, 顺便判 \(0\) 环.
有两个问题不是那么明了:
- 为什么要从 \(n\) 开始搜索?
- 为什么 \(k\) 要从小到大搜索?
第一个问题, 我的理解是 :
假设从 \(1\) 开始搜索, 我们就只知道当前点到起点的距离, 对于它能否到达终点我们是无法直接判断的.
而从 \(n\) 开始搜索的话, 就可以直接判断它是否能到达终点, 并及时停止进一步无用的搜索.
当然, 在反向边上跑最短路然后从 \(1\) 开始搜也是可以的, 相当于交换了起点和终点.
第二个问题 :
其实从大到小也是可以的....
代码
第二次的代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
const int N=100000+7;
const int M=200000+7;
const int K=50+7;
int T,n,m,k;
ll p,f[N][K],ans;
bool b[N],be[N][K],re[N][K],flag;
int dis[N];
int lst[N],nxt[M],to[M],len[M],tot;
int rlst[N],rnxt[M],rto[M],rlen[M],rtot;
void add(int x,int y,int w){
nxt[++tot]=lst[x];
to[tot]=y;
len[tot]=w;
lst[x]=tot;
}
void radd(int x,int y,int w){
rnxt[++rtot]=rlst[x];
rto[rtot]=y;
rlen[rtot]=w;
rlst[x]=rtot;
}
void read(){
tot=rtot=0;
memset(lst,0,sizeof(lst));
memset(rlst,0,sizeof(rlst));
scanf("%d%d%d%lld\n",&n,&m,&k,&p);
int x,y,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
radd(y,x,w);
}
}
queue<int> q;
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(b,0,sizeof(b));
priority_queue<pair<int,int> > h;
h.push(make_pair(0,1));
dis[1]=0;
while(!h.empty()){
int u=h.top().second; h.pop();
if(b[u]) continue;
b[u]=1;
for(int i=lst[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>dis[u]+len[i]){
dis[v]=dis[u]+len[i];
h.push(make_pair(-dis[v],v));
}
}
}
}
int clac(int u,int r){
if(r<0) return 0;
if(re[u][r]){
flag=1;
return 0;
}
if(be[u][r]) return f[u][r];
re[u][r]=1;
for(int i=rlst[u];i;i=rnxt[i]){
int v=rto[i],dif=dis[v]+rlen[i]-dis[u];
f[u][r]=(f[u][r]+clac(v,r-dif))%p;
if(flag) return 0;
}
be[u][r]=1;
re[u][r]=0;
return f[u][r];
}
int main(){
//freopen("park.in","r",stdin);
//freopen("park.out","w",stdout);
cin>>T;
while(T--){
read();
dijkstra();
memset(be,0,sizeof(be));
memset(re,0,sizeof(re));
memset(f,0,sizeof(f));
f[1][0]=1;
be[1][0]=1;
flag=0;
ans=0;
for(int i=0;i<=k;i++){
ans=(ans+clac(n,i))%p;
if(flag) break;
}
if(flag) printf("-1\n");
else printf("%lld\n",ans);
}
return 0;
}
/*
1
5 10 0 624775377
1 2 1
2 5 2
2 4 1
5 4 2
4 2 1
4 5 2
2 3 1
3 2 1
1 3 2
3 5 1
*/