743-网络延迟时间

LeetCode 743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，其中ui是源节点，vi是目标节点，wi是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

method: Dijkstra

可以使用如下结构存储边

vector<vector<pair<int, int>>> edge(n + 1);
for (auto t : times) {
    edge[t[0]].push_back({t[1], t[2]});
}
for (int i = 1; i <= n; i++) {
    for (auto e : edge[i]) {    // 枚举节点i的所有边
        cout << i << "->" << e.first << ": " << e.second << endl;
    }
}
2->1: 1
2->3: 1
3->4: 1

堆优化的Dijkstra

const int inf = 0x3f3f3f3f;
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> edge(n + 1);
    for (auto t : times) {
        edge[t[0]].push_back({t[1], t[2]});
    }
    vector<int> dist(n + 1, inf);   // 各个点到起点的距离初始化为inf
    vector<bool> inq(n + 1, false);
    dist[k] = 0;    // 起点到自己的距离为0
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, k});
    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        int u = x.second;
        if (inq[u]) continue;   // 如果这个点已经入队出队了，说明已经更新为最小了
        inq[u] = true;
        for (auto e : edge[u]) {    // 枚举该点的所有边
            int v = e.first;
            int w = dist[u] + e.second;
            if (dist[v] > w) {      // 更新与该点相连的点的距离
                dist[v] = w;
                q.push({w, v});
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dist[i]);
    }
    return res == inf ? -1 : res;   // 如果有节点的距离为inf，说明该点不可达
}

Dijkstra求单源最短路径，只能求最短路，不能求最长路，不能处理负边权问题