【LeetCode】743. Network Delay Time 图最短路问题

题目是一道求图的最短路问题，此类问题主要有三种经典算法：

① Floyd
② Bellman Ford
③ Dijkstra 

代码如下：

//Floyd
int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        /* Initialization begin*/
        vector<vector<int>> g(N,vector<int>(N,600000));
        int ret=0;
        for(auto it : times)
            g[it[0]-1][it[1]-1] = it[2];
        for(int i=0; i<N; i++)
                for(int j=0; j<N;j++)
                    if(i==j) g[i][j]=0;
        /* Initialization end*/
				
        /* 5 lines floyd-warshall */
        for(int k = 0; k< N; k++)
            for(int i=0; i<N; i++)
                for(int j=0; j<N;j++) 
                    if(g[i][j]>g[i][k]+g[k][j])
                        g[i][j] = g[i][k]+g[k][j];
        
        for(int i=0; i<N; i++){
            if(g[K-1][i]==600000) return -1;
            ret= max(ret, g[K-1][i]);
        }
        return ret;
    }

//Bellman Ford
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<int> dist(N + 1, INT_MAX);
        dist[K] = 0;
        for (int i = 0; i < N; i++) {
            for (vector<int> e : times) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        int maxwait = 0;
        for (int i = 1; i <= N; i++)
            maxwait = max(maxwait, dist[i]);
        return maxwait == INT_MAX ? -1 : maxwait;
    }
};

//Dijkstra
typedef pair<int, int> pii;
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<pii> g[n + 1];
        for (const auto& t : times) {
            g[t[0]].push_back(make_pair(t[1], t[2]));
        }
        const int inf = 1e9;
        vector<int> dist(n + 1, inf);
        dist[k] = 0;
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        pq.push(make_pair(0, k));
        int u, v, w;
		vector<bool> vis(n + 1, false);
        while (!pq.empty()) {
            pii p = pq.top(); pq.pop();
            u = p.second;
			if (vis[u]) continue;
            for (auto& to : g[u]) {
                v = to.first, w = to.second;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push(make_pair(dist[v], v));
                }
            }
			vis[u] = true;
        }
        int ans = *max_element(dist.begin() + 1, dist.end());
        return ans == inf ? -1 : ans;
    }
};

补充知识：C++ pair的用法