leetcode743

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int,multimap<int,int>> graph=buildGraph(times);
        vector<int> distance(n + 1, INT_MAX);
        distance[k]=0;
        deque<int> que;
        que.push_back(k);
        int cnt=0;//count the node
        bool noted[n+1];
        memset(noted,0,(n+1)*sizeof(bool));
        noted[k]=true;
        multimap<int,int> min_que;//剩余未遍历点的路径最短的优先队列
        while(!que.empty()){
            //cout<<1<<endl;
            int tmp=que.front();
            que.pop_front();
            ++cnt;
            if(graph.count(tmp)){
                //cout<<2<<endl;
                multimap<int,int> & edges=graph.at(tmp);
                for (auto edge = edges.begin(); edge != edges.end(); ++edge) {
                    //cout<<3<<endl;
                    if(distance[edge->second]>distance[tmp]+edge->first){
                        min_que.emplace(distance[tmp]+edge->first,edge->second);
                    }
                    distance[edge->second]=min(distance[edge->second],distance[tmp]+edge->first);
                }
            }
            while(!min_que.empty()){
                auto cost=min_que.begin();
                if(!noted[cost->second]){
                    que.push_back(cost->second);
                    noted[cost->second]=1;
                    min_que.erase(min_que.begin());
                    break;
                }
                min_que.erase(min_que.begin());
            }
        }
        if(cnt!=n){
            return -1;
        }
        int ret=0;
        for(int i=1;i<=n;++i){
            //cout<<distance[i]<<endl;
            ret=max(distance[i],ret);
        }
        return ret;
    }
    private:
    template <typename T>
    unordered_map<T,multimap<T,int>> buildGraph(vector<vector<T>>& times) {
        unordered_map<T,multimap<T,int>> g;
        for(auto a:times){
            g[a[0]].insert(pair <int, int> (a[2],a[1]));
            //g[a[0]].emplace(a[1],a[2]);
        }
        return g;
    }
};