743. Network Delay Time --- M !!!!!!

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

 

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

A：

Dijkstra's Algorithm

class Solution {

public:

int networkDelayTime(vector<vector<int>>& times, int n, int k) {

// Dijkstra algorithm

vector<bool> visited(n+1, false);

vector<int> minDist(n+1, INT_MAX);

minDist[k] = 0;

unordered_map<int, vector<pair<int, int>>> Edges;

for(const auto & edge : times){// map edge by starting node

Edges[edge[0]].push_back({edge[1], edge[2]});

}

while(true){

// find the one with lowese distance

int curMinDist = INT_MAX;

int u = -1;

for(int i = 1 ; i <= n; i ++){

if(not visited[i] && minDist[i] < curMinDist){

curMinDist= minDist[i];

u = i;

}

}

if(curMinDist == INT_MAX)

break;

visited[u] = true;

// update minimum distance originating from u

for(const auto & p : Edges[u]){

int v = p.first, w = p.second;

if(not visited[v] && minDist[u] + w < minDist[v]){

minDist[v] = minDist[u] + w;

}

}

}

auto max_element_it = max_element(minDist.begin()+1, minDist.end());

return *max_element_it == INT_MAX? -1 : *max_element_it;

}

};

Mistakes：

node index的范围是1 到n。  我默认一开始还是写成了0 到 n-1。