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

#ifndef LEETCODE_SOLUTION34_H
#define LEETCODE_SOLUTION34_H
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Solution34 {
public:
    typedef pair<int, int> PII;
    // 单源最短路径，先求出点0到所有大点的最短路径dist。
    // 然后遍历每条边，从每条边的两端大点出发，求出剩余maxMoves-dist[i]步时，能走多少个小点
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        const int INF=INT_MAX/2;
        vector<vector<PII>>graph(n);
        for(auto e:edges){
            graph[e[0]].push_back(make_pair(e[1],e[2]));
            graph[e[1]].push_back(make_pair(e[0],e[2]));
        }
        vector<int>dist(n,INF);
        dist[0]=0;
        priority_queue<PII,vector<PII>,greater<PII>>pq;
        pq.emplace(0,0);
        while(!pq.empty()){
            auto [d,u]=pq.top();
            pq.pop();
            if(d>dist[u])
                continue;
            for(auto &[v,w]:graph[u]){
                if(dist[u]+w+1<dist[v]){
                    dist[v]=dist[u]+w+1;
                    pq.emplace(dist[v],v);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++)
            if(dist[i]<=maxMoves){
                res++;
            }
        for(auto &edge:edges){
            int start=edge[0];
            int end=edge[1];
            int cnt=edge[2];
            int sum=0;
            sum+=dist[start]<=maxMoves?maxMoves-dist[start]:0;
            sum+=dist[end]<=maxMoves?maxMoves-dist[end]:0;
            res+=min(sum,cnt);
        }
        return res;
    }
};


#endif //LEETCODE_SOLUTION34_H