肯定要先跑一次最短路
题目中的k 相当于允许我们走k距离的“冤枉路”
回想之前有些题是如何判断哪些边是属于最短路上的 当dis[now]+edge[u].val==dis[vis] 这条边就在最短路上
类似的 我们可以得出 dis[now]+edge[u].val-dis[vis]就是这一次走的“冤枉路”的长度
到这个地方搜索的策略已经很明显了 dfs(now,remain)表示当前当前点为now 还剩remain的冤枉路可以走
边界条件：remain<0
然后发现这玩意儿不用标记vis数组 因为就算有环 remain会一直减下去直到<0 还可以记忆化一下
不过无穷多的情况肿么判？
可以这样想 为什么数据会给你有没有0边？
回忆最短路计数就会问你有没有无穷多条满足要求的路 这种情况只有可能是有0环存在
在这道题里判0环异常容易 假如进入了0环 那肯定会绕了一圈后 又回到当前点 且remain不变
因此标记一下就好
另外 还有一个坑点 这是有向图 很有可能有些点无法到达终点
因此还要反向搜出那些不能到达的
#include<bits/stdc++.h> #define N 100005 #define M 200005 #define INF 0x3f3f3f3f using namespace std; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); } struct Edge { int to,next,val; }edge[2*M]; struct Node { int to,val; Node(int to,int val):to(to),val(val){} }; int n,m,k,p,tot,first[N],dis[N]; inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } vector<Node> res[N]; typedef pair<int,int> Pair; bool visit[N],able[N]; void Dijkstra(int s) { memset(dis,0x3f,sizeof(dis)); memset(visit,false,sizeof(visit)); priority_queue<Pair,vector<Pair>,greater<Pair> > heap; heap.push(make_pair(0,s)); dis[s]=0; while(!heap.empty()) { int now=heap.top().second; heap.pop(); if(visit[now]) continue; visit[now]=true; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dis[now]+edge[u].val<dis[vis]) { dis[vis]=dis[now]+edge[u].val; heap.push(make_pair(dis[vis],vis)); } } } } void dfs1(int now) { able[now]=true; for(int i=0;i<res[now].size();i++) { int vis=res[now][i].to; if(!able[vis]) dfs1(vis); } } int f[N][55],again[N][55]; int dfs(int now,int remain) { if(remain<0) return 0; //越界了 if(again[now][remain]) return -INF; //走到零环了 普通的环不用担心 因为remain会一直减下去 if(f[now][remain]!=-1) return f[now][remain]; //记忆化 int temp=0; //统计当前答案 again[now][remain]=1; if(now==n) temp++; //到达了n for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(!able[vis]) continue; int key=dfs(vis,remain-(edge[u].val-(dis[vis]-dis[now])))%p; if(key==-INF) //零环 return -INF; else temp=(temp+key)%p; } again[now][remain]=0; f[now][remain]=temp%p; return f[now][remain]; } void init() { memset(edge,0,sizeof(edge)); memset(first,0,sizeof(first)); tot=0; memset(f,-1,sizeof(f)); memset(able,0,sizeof(able)); memset(again,0,sizeof(again)); } int main() { int T; read(T); while(T--) { init(); read(n),read(m),read(k),read(p); for(int i=1;i<=n;i++) res[i].clear(); for(int i=1,x,y,z;i<=m;i++) { read(x),read(y),read(z); addedge(x,y,z); res[y].push_back(Node(x,z)); } Dijkstra(1); dfs1(n); int Q=dfs(1,k); if(Q<0) cout<<"-1"<<'\n'; else cout<<Q<<'\n'; } }转载于:https://www.cnblogs.com/Patrickpwq/p/9894055.html
