//
// Created by 高森森 on 2022/2/7.
//

#ifndef LEETCODE_SOLUTION22_H
#define LEETCODE_SOLUTION22_H

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution22 {
public:
    //堆优化的迪捷斯特拉+记忆化dfs
    const int kMod=1e9+7;
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>>g(n+1);
        //建图
        for(auto edge:edges){
            g[edge[0]].emplace_back(edge[1],edge[2]);
            g[edge[1]].emplace_back(edge[0],edge[2]);
        }
        //dijkstra
        vector<int>dist(n+1,INT_MAX);
        dist[n]=0;
        //优先队列三个参数，数据类型，容器类型：默认vector，比较方式，stl中有greater和less
        //优先队列中的pair的first为距离，second为n点到某一点的距离，dis[n]=0;
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
        q.emplace(0,n);
        while(!q.empty()){
            pair<int,int>node=q.top();
            q.pop();
            int d=node.first;
            int u=node.second;
            if(d>dist[u]){
                continue;
            }
            for(auto neigh:g[u]){
                int v=neigh.first;
                int w=neigh.second;
                if(dist[v]>dist[u]+w)
                    q.emplace(dist[v]=dist[u]+w,v);
            }
        }
        //迪杰斯特拉求除最短路径后，记忆化dfs
        vector<int>dp(n+1,INT_MAX);
        return dfs(1,n,dist,g,dp);
    }
    //记忆化dfs
    int dfs(int u,int n,vector<int>&dist, vector<vector<pair<int,int>>>&g,vector<int>&dp){
        if(u==n)
            return 1;
        if(dp[u]!=INT_MAX)
            return dp[u];
        int ans=0;
        for(auto node:g[u]){
            if(dist[node.first]<dist[u]){
                ans=(ans+dfs(node.first,n,dist,g,dp))%kMod;
            }
        }
        dp[u]=ans;
        return dp[u];
    }
};


#endif //LEETCODE_SOLUTION22_H