https://leetcode.com/problems/network-delay-time/description/, we need to go to every node from K, calculate the max weight.
Dijkstra:
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { unordered_map<int,unordered_map<int,int>> v; for (const auto& t : times) v[t[0]-1].insert( {t[1]-1,t[2]} ); vector<int> cost(N, INT_MAX); unordered_set<int> g2; //g1.insert(K-1); for (int i = 0; i < N; i++) g2.insert(i); g2.erase(K-1); for (const auto& nb : v[K-1]) cost[nb.first] = nb.second; cost[K-1] = 0; while (!g2.empty()) { int next = -1; for (auto i : g2) if (next == -1 || cost[i] < cost[next]) next = i; if (next == -1 || cost[next] == INT_MAX) return -1; // impossible g2.erase(next); //g1.insert(next); for (const auto& nb : v[next]) if (cost[next] + nb.second < cost[nb.first]) cost[nb.first] = cost[next] + nb.second; } int maxCost = 0; for (auto i : cost) maxCost = max(maxCost, i); return maxCost; } };
BFS:
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<unordered_map<int,int>> v(N); for (const auto& t : times) v[t[0]-1].insert( {t[1]-1,t[2]} ); vector<int> cost(N, INT_MAX); cost[K-1] = 0; queue<int> q; q.push(K-1); while (!q.empty()) { int cur = q.front(); q.pop(); for (const auto& nb : v[cur]) { if (cost[cur] + nb.second < cost[nb.first]) { cost[nb.first] = cost[cur] + nb.second; q.push(nb.first); } } } int maxCost = 0; for (auto i : cost) maxCost = max(maxCost, i); return maxCost == INT_MAX ? -1 : maxCost; } };
Bellman Ford:
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int N, int K) { vector<int> cost(N+1, INT_MAX); cost[K] = 0; while (true) { bool changed = false; for (const auto& t : times) { // t[0]->t[1]: t[2] if (cost[t[0]] < cost[t[1]] - t[2]) { // consider overflow cost[t[1]] = cost[t[0]] + t[2]; changed = true; } } if (!changed) break; } int maxCost = 0; for (int i = 1; i <= N; i++) maxCost = max(maxCost, cost[i]); return maxCost == INT_MAX ? -1 : maxCost; };