题意分析

1786. 从第一个节点出发到最后一个节点的受限路径数 - 力扣（LeetCode）1976. 到达目的地的方案数 - 力扣（LeetCode）

        这两题解法一样，建议先做1976，就是最短路+记忆化搜索，只是本题在动态规划时在回溯时加了个递减的限制条件，且不要求是最短路。

算法思路

1. 先以终点为起点算出最短路径。
2. 以终点开始回溯，如果下一点的路径长度小于等于当前的路径长度，不合条件，就不进入递归，否则就递归求值。

代码实现

#define maxn 20001
using ll=long long;
typedef pair<int,ll> PII;
const ll inf=LLONG_MAX/2;
const int modi=1e9+7;
class Solution {vector<PII>  g[maxn];ll dist[maxn];ll pathnum[maxn];
public:int countRestrictedPaths(int n, vector<vector<int>>& edges) {for(int i=0;i<n;i++){dist[i]=inf;pathnum[i]=-1;}for(auto & e:edges){int x=e[0]-1,y=e[1]-1,w=e[2];g[x].emplace_back(y,w);g[y].emplace_back(x,w);}priority_queue<PII,vector<PII>,greater<>> q;q.emplace(0,n-1);while(!q.empty()){auto [d,i]=q.top();q.pop();if(dist[i]<inf) continue;dist[i]=d;for(auto & [nxt,w]:g[i]){if(dist[nxt]<inf) continue;q.emplace(d+w,nxt);}}return dfs(n-1,0);}ll dfs(int cur,int end){if(cur==end) return 1;if(pathnum[cur]!=-1) return pathnum[cur];long long ans=0;for(auto & [nxt,w]:g[cur]){if(dist[cur]>=dist[nxt]) continue;ans+=dfs(nxt,end);ans%=modi;                }pathnum[cur]=ans;return ans;}
};

解题总结

        注意距离数组从谁开始，遍历次序，题设条件，还有数据范围是long long，否则溢出报错。