
思路:计算最短路径的数量时,我们只需要在计算时dp即可,dp[i]代表走到i时的总路径
class Solution {
public:int countPaths(int n, vector<vector<int>>& edges) {vector<vector<tuple<int, long long, long long>>>ed(n);int c = 0;for(auto it : edges){ed[it[0]].push_back({it[1], it[2], c});ed[it[1]].push_back({it[0], it[2], c});c ++;}vector<long long>dis(n, 1000000000000000000), st(n);priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>q;q.push({0, 0});dis[0] = 0;vector<long long>dp(n);dp[0] = 1;while(q.size()){auto [d, x] = q.top();q.pop();if(x == n - 1){return dp[n - 1] % 1000000007;}if(st[x]) continue;st[x] = 1;for(auto [u, v, i] : ed[x]){if(dis[u] > dis[x] + v){dis[u] = dis[x] + v;dp[u] = dp[x];q.push({dis[u], u}); }else if(dis[x] + v == dis[u]){dp[u] = (dp[u] + dp[x]) % 1000000007;}}}return dp[n - 1];}
};