[leetcode]1786. 从第一个节点出发到最后一个节点的受限路径数(Dijkstra+记忆化搜索/dp)

题目链接

题意

给定一个无向连通图，edges={u,v,w} 表示$u$和$v$之间有一条无向边，边权为$w$
$n$个点 $[1,n]$ 每个点到$n$的最短路为$dis[i]$
定义受限路径: 从起点$1$到$n$，路径上的$dis[i]$递减
求1->n的受限路径方案数

方法一 Dijkstra+记忆化搜索

思路

通过Dijkstra预处理出每个点距离$n$的最短路
通过dfs枚举每种方案 加上记忆化 避免超时

Code

using ll = long long;
#define pii pair<int,int>
#define ar2 array<ll,2>
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int a[N];
class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<ar2>>g(n+1);
        for(auto e:edges){
            int u=e[0],v=e[1],w=e[2];
            g[u].push_back({w,v});
            g[v].push_back({w,u});
        }

        vector<ll>dis(n+1,LINF);//注意要用LINF，INF太小了
        dis[n]=0;
        priority_queue<pii,vector<pii>,greater<>>pq;
        pq.emplace(0,n);

        while(pq.size()){
            auto [d,i]=pq.top();pq.pop();
            if(d>dis[i]) continue;

            for(auto [w,j]:g[i]){
                if(dis[j]>d+w){
                    dis[j]=d+w;
                    pq.emplace(dis[j],j);
                }
            }
        }
        // if(dis[1]==LINF) return 0;
        for(int i=1;i<=n;i++){
            if(dis[i]==LINF) dis[i]=-1;
        }

        cout<<dis[1]<<endl;

        vector<ll>memo(n+1,-1);
        function<ll(int)>dfs=[&](int i)->ll{
            if(i==n) return 1;
            if(memo[i]!=-1) return memo[i];

            int ret=0;
            for(auto [w,j]:g[i]){
                if(dis[i]>dis[j]){
                    ret=(ret+dfs(j))%MOD;
                }
            }
            // printf("dfs(%d),retrun %d\n",i,ret%MOD);
            memo[i]=ret%MOD;
            return memo[i];
        };
        
        return dfs(1)%MOD;

    }
};

实现细节

• 注意 Dijkstra要从终点$n$开始扩展最短路，因为$dis[i]$在此题中表示$i$到$n$的距离，跟常见的Dijkstra不同 不是表示$i$到$1$的距离
  记得开longlong，并且无穷大也要用longlong的max来表示，不然有一个样例过不去

方法二 Dijkstra+dp

思路

思路同上，把记忆化搜索改成dp，我感觉没有记忆化搜索直观，但是能快一点点

Code

using ll = long long;
#define pii pair<int,int>
#define ar2 array<ll,2>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=1e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<ar2>>g(n+1);
        for(auto e:edges){
            int u=e[0],v=e[1],w=e[2];
            g[u].push_back({w,v});
            g[v].push_back({w,u});
        }

        vector<ll>dis(n+1,LINF);
        dis[n]=0;
        priority_queue<pii,vector<pii>,greater<>>pq;
        pq.emplace(0,n);

        while(pq.size()){
            auto [d,i]=pq.top();pq.pop();
            if(d>dis[i]) continue;

            for(auto [w,j]:g[i]){
                if(dis[j]>d+w){
                    dis[j]=d+w;
                    pq.emplace(dis[j],j);
                }
            }
        }
        // if(dis[1]==LINF) return 0;
        for(int i=1;i<=n;i++){
            if(dis[i]==LINF) dis[i]=-1;
        }

        vector<int>idx(n);
        iota(idx.begin(),idx.end(),1);
        sort(idx.begin(),idx.end(),[&](int a,int b){
            return dis[a]<dis[b];
        });//按最短路从小到大排序

        vector<ll>dp(n+1);//dp[i]表示从i到n的方案数
        dp[n]=1;
        for(int i:idx){
            for(auto [_,j]:g[i]){
                if(dis[i]>dis[j]){
                    dp[i]=(dp[i]+dp[j])%MOD;
                }
            }
        }
        
        return dp[1];
    }
};

实现细节

根据最短路从小到大更新dp
因为受限路径要求dp[i]要根据dis小于dis[i]的值更新