# Dijkstra 演算法
- [Please Share dijkstra's algorithm questions](https://leetcode.com/discuss/interview-question/731911/please-share-dijkstras-algorithm-questions)

class Solution {
    vector<pair<int, int> > G[101];
    int dis[101];
    struct node{
        int id, dis;
        bool operator < (const node &rhs) const{
            return dis > rhs.dis;
        }
    };
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        for(int i=0;i<times.size();i++){
            G[times[i][0]].push_back({times[i][1], times[i][2]});
        }
        for(int i=1;i<=n;i++)   dis[i]=-1;
        
        dis[k] = 0;
        priority_queue<node> pq;
        pq.push({k, 0});
        while(!pq.empty()){
            node tmp = pq.top(); pq.pop();
            int id=tmp.id;
            for(auto e:G[id]){
                int nb = e.first;
                int dd = e.second;
                if(dis[nb]==-1 || dis[id]+dd < dis[nb]){
                    dis[nb] = dis[id]+dd;
                    pq.push({nb, dis[nb]});
                }
            }
        }
        
        int ans = 0;
        for(int i=1;i<=n;i++){
            if(dis[i]==-1)  return -1;
            ans = max(ans, dis[i]);
        }
        return ans;
    }
};