class Solution {
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k) {
const int inf = INT_MAX / 2;
vector<vector<int>> g(n, vector<int>(n, inf));
for (auto &t : times) {
int x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];
}
vector<int> dist(n, inf);
dist[k - 1] = 0;
vector<int> used(n);
for (int i = 0; i < n; ++i) {
int x = -1;
for (int y = 0; y < n; ++y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;
for (int y = 0; y < n; ++y) {
dist[y] = min(dist[y], dist[x] + g[x][y]);
}
}
int ans = *max_element(dist.begin(), dist.end());
return ans == inf ? -1 : ans;
}
};
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
final int INF = Integer.MAX_VALUE / 2;
int[][] g = new int[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], INF);
}
for (int[] t : times) {
int x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];
}
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[k - 1] = 0;
boolean[] used = new boolean[n];
for (int i = 0; i < n; ++i) {
int x = -1;
for (int y = 0; y < n; ++y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;
for (int y = 0; y < n; ++y) {
dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
}
}
int ans = Arrays.stream(dist).max().getAsInt();
return ans == INF ? -1 : ans;
}
}
/**
* @param {number[][]} times
* @param {number} n
* @param {number} k
* @return {number}
*/
var networkDelayTime = function(times, n, k) {
const INF = Number.MAX_SAFE_INTEGER;
const g = new Array(n).fill(INF).map(() => new Array(n).fill(INF));
for (const t of times) {
const x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];
}
const dist = new Array(n).fill(INF);
dist[k - 1] = 0;
const used = new Array(n).fill(false);
for (let i = 0; i < n; ++i) {
let x = -1;
for (let y = 0; y < n; ++y) {
if (!used[y] && (x === -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;
for (let y = 0; y < n; ++y) {
dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
}
}
let ans = Math.max(...dist);
return ans === INF ? -1 : ans;
};
func networkDelayTime(times [][]int, n, k int) (ans int) {
type edge struct{ to, time int }
g := make([][]edge, n)
for _, t := range times {
x, y := t[0]-1, t[1]-1
g[x] = append(g[x], edge{y, t[2]})
}
const inf int = math.MaxInt64 / 2
dist := make([]int, n)
for i := range dist {
dist[i] = inf
}
dist[k-1] = 0
h := &hp{{0, k - 1}}
for h.Len() > 0 {
p := heap.Pop(h).(pair)
x := p.x
if dist[x] < p.d {
continue
}
for _, e := range g[x] {
y := e.to
if d := dist[x] + e.time; d < dist[y] {
dist[y] = d
heap.Push(h, pair{d, y})
}
}
}
for _, d := range dist {
if d == inf {
return -1
}
ans = max(ans, d)
}
return
}
type pair struct{ d, x int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].d < h[j].d }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }
func max(a, b int) int {
if a > b {
return a
}
return b
}
func networkDelayTime(times [][]int, n, k int) (ans int) {
const inf = math.MaxInt64 / 2
g := make([][]int, n)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
}
}
for _, t := range times {
x, y := t[0]-1, t[1]-1
g[x][y] = t[2]
}
dist := make([]int, n)
for i := range dist {
dist[i] = inf
}
dist[k-1] = 0
used := make([]bool, n)
for i := 0; i < n; i++ {
x := -1
for y, u := range used {
if !u && (x == -1 || dist[y] < dist[x]) {
x = y
}
}
used[x] = true
for y, time := range g[x] {
dist[y] = min(dist[y], dist[x]+time)
}
}
for _, d := range dist {
if d == inf {
return -1
}
ans = max(ans, d)
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
'''
Dijkstra 最短路径算法
'''
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = [[] for _ in range(n)]
for x, y, time in times:
g[x - 1].append((y - 1, time))
dist = [float('inf')] * n
dist[k - 1] = 0
q = [(0, k - 1)]
while q:
time, x = heapq.heappop(q)
if dist[x] < time:
continue
for y, time in g[x]:
if (d := dist[x] + time) < dist[y]:
dist[y] = d
heapq.heappush(q, (d, y))
ans = max(dist)
return ans if ans < float('inf') else -1
'''
Dijkstra 最短路径算法
'''
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
g = [[float('inf')] * n for _ in range(n)]
for x, y, time in times:
g[x - 1][y - 1] = time
dist = [float('inf')] * n
dist[k - 1] = 0
used = [False] * n
for _ in range(n):
x = -1
for y, u in enumerate(used):
if not u and (x == -1 or dist[y] < dist[x]):
x = y
used[x] = True
for y, time in enumerate(g[x]):
dist[y] = min(dist[y], dist[x] + time)
ans = max(dist)
return ans if ans < float('inf') else -1
