题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。
注意:图中可能 存在负权回路 。
bellman_ford
注意:存在负权边,可能存在负权回路
思路:分轮次更新所有边,通过已知节点来更新相邻节点的权重。避免跨轮次更新
举例:1—>2—>3 以及 1—>3 初始化所有权重都为0x3f3f3f3f, dist[1]=0
1)第一轮:点1已知,更新所有与1相邻的点的值能得到更新,
即(1–>2; 1–直接到–>3;其中1–>2–>3不能直接更新,需要等到下一轮)
2)第二轮:更新1–>2; 1–直接到–>3;1–>2–>3通过上轮更新后的2到达3
tips:每次都会遍历所有的边和权重
具体代码
import java.util.*;
import java.io.*;
public class Main {
private static int N = 510;
private static int INF = 0x3f3f3f3f;
private static int[] dist = new int[N];
private static int[] last = new int[N];
private static List<int[]> edges = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
int k = Integer.parseInt(line[2]);
Arrays.fill(dist, INF);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int a = Integer.parseInt(line[0]);
int b = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
edges.add(new int[]{a, b, w});
}
int res = bellmanFord(n, m, k);
if (res == -1) System.out.println("impossible");
else System.out.println(res);
}
private static int bellmanFord(int n, int m, int k) {
dist[1] = 0;
for (int i=0; i<k; i++) {
// 记录上轮数据
for (int u=0; u<=n; u++) {
last[u] = dist[u];
}
// 遍历所有边
for (int j=0; j<m; j++) {
int[] edge = edges.get(j);
int a = edge[0];
int b = edge[1];
int w = edge[2];
dist[b] = Math.min(dist[b], last[a] + w);
}
}
if (dist[n] >= (INF>>1)) return -1;
return dist[n];
}
}