leetcode743

Dijkstra算法

https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

dijkstra Bellman_Ford与Floyd算法的性质比较与实现

https://blog.csdn.net/jxlincong/article/details/44887111

Bellman_Ford

https://www.codenong.com/cs106059004/

三种算法题解

https://www.cnblogs.com/grandyang/p/8278115.html

 为什么std :: multimap比std :: priority_queue慢

https://www.codenong.com/41807720/

算法 - 优先队列 - 斐波那契堆

https://redspider110.github.io/2018/09/25/0105-algorithms-fibonacci-heap/

https://www.cnblogs.com/skywang12345/p/3659060.html

https://stackoverflow.com/questions/504823/has-anyone-actually-implemented-a-fibonacci-heap-efficiently

https://www.cnblogs.com/frankcui/p/12088422.html

https://www.cs.au.dk/~gerth/papers/stoc12.pdf

https://www.cs.au.dk/~gerth/papers/soda96.pdf

1.dijkstra实现

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;
        int que=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!=-1){
            //cout<<1<<endl;
            int tmp=que;
            que=-1;
            ++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=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;
    }
};

 改用优先队列

struct node
{
    int x, y;
    node(int x,int y):x(x),y(y){}
};
 
struct cmp
{
    bool operator()(node a,node b)
    {
        if(a.x == b.x)  return a.y >= b.y;
        else return a.x > b.x;
    }
};
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;
        int que=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;//剩余未遍历点的路径最短的优先队列
        priority_queue<node,vector<node>,cmp> min_que;
        while(que!=-1){
            //cout<<1<<endl;
            int tmp=que;
            que=-1;
            ++cnt;
            if(cnt>n){
                return -1;
            }
            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);
                        min_que.emplace(node(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=cost->second;
                //    noted[cost->second]=1;
                //    min_que.erase(min_que.begin());
                //    break;
                //}
                //min_que.erase(min_que.begin());
                auto cost=min_que.top();
                if(!noted[cost.y]){
                    //cout<<cost.x<<":"<<cost.y<<endl;
                    que=cost.y;
                    noted[cost.y]=1;
                    min_que.pop();
                    break;
                }
                min_que.pop();
            }
        }
        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;
    }
};