【Leetcode】1786. Number of Restricted Paths From First to Last Node

题目地址：

https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/description/

给定一个n nn个点m mm条边的无向非负权图，顶点编号为1 ∼ n 1\sim n1∼n，每个点到n nn可以求出最短距离，记为d [ u ] d[u]d[u]；问从1 11到n nn存在多少条满足d [ 1 ] > d [ i 1 ] > d [ i 2 ] > . . . > d [ n ] d[1]>d[i_1]>d[i_2]>...>d[n]d[1]>d[i1​]>d[i2​]>...>d[n]的路径。答案对1 0 9 + 7 10^9+7109+7取模。

为了求每个点到点n nn的最短路，可以用Dijkstra算法来做，以n nn为源点即可。接着，设f [ u ] f[u]f[u]是从u uu出发到n nn的满足条件的路径数，则有：f [ u ] = ∑ u → v ∧ d [ u ] > d [ v ] f [ v ] f[u]=\sum_{u\to v \land d[u]>d[v]} f[v]f[u]=u→v∧d[u]>d[v]∑​f[v]边界条件f [ n ] = 1 f[n]=1f[n]=1。可以用记忆化搜索来做。代码如下：

classSolution{public:usingPII=pair<int,int>;intcountRestrictedPaths(intn,vector<vector<int>>&es){staticconstexprintINF=2e9,MOD=1e9+7;intm=es.size();vector<int>h(n+1,-1),e(m<<1),ne(m<<1),w(m<<1);intidx=0;autoadd=[&](inta,intb,intc){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;};for(auto&e:es){inta=e[0],b=e[1],c=e[2];add(a,b,c);add(b,a,c);}vector<int>dist(n+1,INF);dist[n]=0;vector<bool>vis(n+1);priority_queue<PII,vector<PII>,greater<>>heap;heap.push({0,n});while(heap.size()){auto[d,u]=heap.top();heap.pop();if(vis[u])continue;vis[u]=true;for(inti=h[u];~i;i=ne[i]){intv=e[i];if(dist[v]>d+w[i]){dist[v]=d+w[i];heap.push({dist[v],v});}}}vector<int>f(n+1,-1);autodfs=[&](auto&&self,intu)->int{if(~f[u])returnf[u];if(u==n)returnf[u]=1;f[u]=0;for(inti=h[u];~i;i=ne[i]){intv=e[i];if(dist[v]<dist[u])f[u]=(f[u]+self(self,v))%MOD;}returnf[u];};returndfs(dfs,1);}};

时间复杂度O ( m log ⁡ n + m + n ) O(m\log n+m+n)O(mlogn+m+n)，空间O ( m + n ) O(m+n)O(m+n)。