不知不觉做了100道leetcode了，
今天这道是最短路模板题，好题。

class Solution {
public:
    vector<vector<int>> g;
    vector<int> dist;
    vector<int> st;
    int nz;
    void dijkstra(int k){
        dist[k]=0;
        for(int i=1;i<=nz;i++){
            int t=-1;
            for(int j=1;j<=nz;j++)
                if(!st[j]&&(t==-1||dist[t]>dist[j]))
                    t=j;
            for(int j=1;j<=nz;j++)
                dist[j]=min(dist[j],dist[t]+g[t][j]);
            st[t]=true;
        }
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        nz=n;
        g=vector<vector<int>>(n+1,vector<int>(n+1,0x3f3f3f3f));
        dist.resize(n+1,0x3f3f3f3f);
        st.resize(n+1,0);

        for(auto &x: times){
            g[x[0]][x[1]]=min(g[x[0]][x[1]],x[2]);
        }
        dijkstra(k);
        int res=1;
        for(int i=1;i<=n;i++) res=max(res,dist[i]);

        if(res==0x3f3f3f3f) return -1;
        return res;
    }
};