lc1976. 到达目的地的方案数

题目链接：

题解

最短路，堆优化

参考代码

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        int mod = 1e9+7;
        long long dp[300];
        long long mp[300][300];
        long long cnt[300];
        int u[300];

        // vector<vector<pair<int,long long>>>mp[300];
        for(int i=0;i<n;i++) {
            dp[i]=0x7fffffffffffffff;
            cnt[i]=0;
            u[i]=0;
            // mp[i].clear();
        }
        memset(mp, 0xff, sizeof mp);
        for(auto r:roads) {
            mp[r[0]][r[1]] = r[2];
            mp[r[1]][r[0]] = r[2];
            // mp[r[0]].push_back(make_pair(r[1], r[2]));
            // mp[r[1]].push_back(make_pair(r[0], r[2]));
        }
        dp[0]=0;
        cnt[0]=1;
        using Pair = pair<long long, int>;
        priority_queue<Pair, vector<Pair>, greater<Pair>> Q;  // 小根堆
        Q.push(Pair(0, 0));
    
        while (!Q.empty()) {
            auto k = Q.top().second;
            // cout<<k<<endl;
            Q.pop();
            if(u[k]) continue;
            u[k]=1;
            for (int i = 0; i < n; i++) {
                // cout<<i<<"->"<<k<<", "<<mp[k][i]<<" "<<Q.size()<<endl;
                if (mp[k][i] !=-1 && dp[k] + mp[k][i] <= dp[i]) {
                    
                if(dp[k]+mp[k][i]==dp[i]) {
                    cnt[i] += cnt[k];
                }
                else {
                    cnt[i] = cnt[k];  
                } 
                dp[i] = dp[k] + mp[k][i];
                cnt[i] %= mod;
                Q.push(Pair(dp[i], i));
                
              }
            }
          }
        return cnt[n-1];
    }
};