题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。
请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。
注意:图中可能 存在负权回路 。
输入格式
第一行包含三个整数n,m,k。
接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。
如果不存在满足条件的路径,则输出“impossible”。
数据范围
1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过10000。
输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3
思路
Bellman-Ford 也属于单源最短路径算法,支持负权边,还能检测出是否有负权环
算法原理:对所有的边m进行 n - 1次松弛操作(n是节点数量),得到所有可能的最短路径
时间复杂度:O(nm) ,m 是边数量,n是节点数量
实例
一共8条边
假设每次松弛操作的顺序是:DC、DF、BC、ED、EF、BE、AE、AB
总结
初始化 dist[1] = 0;
for i in 0, … , n - 1 //n个顶点,如果题目限制了寻找最后节点的次数k,则遍历次数改为k
for 所有边 记作a, b, w
backup(dist) //备份上一次的结果
//松弛操作,找最短路径
dist[b] = min(dist[b], dist[a] + w)
细节:
备份backup
题目中给出
1 -> 2 w12 = 1
2 -> 3 w23 = 1
1 -> 3 w13 = 3
限制遍历次数k = 1
backup(dist) 初始距离dist[1] = 0 dist[2] = INF dist[3] = INF
k = 1;
1 -> 2 2 -> 3 1 -> 3 顺序来进行松弛操作
利用backup更新 距离dist[1] = 0 dist[2] = 1 dist[3] = 3 ((backup[2] = inf) + (w23= 3)) > inf,dist[3] 不更新, 只有1 -> 3 0 + 3 = 3更新)
不是用backup更新,可能发生串联 距离dist[1] = 0 dist[2] = 1 dist[3] = 2 ((dist[2] = 1) + (w23 = 1)) = 2, 1 - > 3 0 + 3 = 3 > 2, 不更新)
实际上,在边数限制的情况下,走w13是最佳选择
0x3f3f3f/2:
java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 10010;
static int V = 0x3f3f3f3f;
static int n, m, k;
static int[] dist = new int[N], backup = new int[N];
static Edge[] edges = new Edge[N];
private static class Edge {
private int a;
private int b;
private int w;
Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
private static int bellmanFord() {
Arrays.fill(dist, V);
dist[1] = 0;
for (int i = 0; i < k; i++) {
backup = dist.clone();
// backup = Arrays.copyOf(dist, N);
for (int j = 0; j < m; j++) {
Edge edge = edges[j];
int a = edge.a;
int b = edge.b;
int w = edge.w;
dist[b] = Math.min(dist[b], backup[a] + w);
}
}
if (dist[n] > V / 2) return V;
return dist[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt();
Edge[] edge = new Edge[N];
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt(), w = sc.nextInt();
edges[i] = new Edge(a, b, w);
}
int t = bellmanFord();
if (t == V) {
System.out.println("impossible");
} else {
System.out.println(t);
}
}
}
c++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];//backup对上一次结果的备份
struct Edge{
int a, b, w;
}edges[M];
int bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; i ++){
memcpy(backup, dist, sizeof dist);
//遍历所有的边
for(int j = 0; j < m; j ++){
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
return dist[n];
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i < m; i ++){
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = bellman_ford();
if(t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
}