有邊數限制的最短路

題目描述

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出從1號點到n號點的最多經過k條邊的最短距離，如果無法從1號點走到n號點，輸出impossible。

注意：圖中可能 存在負權回路 。

輸入格式

第一行包含三個整數n，m，k。

接下來m行，每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z。

輸出格式

輸出一個整數，表示從1號點到n號點的最多經過k條邊的最短距離。

如果不存在滿足條件的路徑，則輸出“impossible”。

數據范圍

$1\le n,k\le 500,$
$1\le m\le 10000,$

任意邊長的絕對值不超過10000。

輸入樣例：3 3 1
1 2 1
2 3 1
1 3 3輸出樣例：3

Solution

Bellman-Ford算法

時間復雜度 $O(nm)$, n 表示點數，m 表示邊數

一般 spfa 性能比 Bellman-Ford 好，只有特殊情況下用 Bellman-Ford 算法，比如這題有邊的數量的限制

1. 思路

for n 次for 所有邊 a,b,wdist[b] = min(dist[b], dist[a] + w)

2. 解題代碼

import java.util.*;
import java.io.*;class Main{// 稀疏圖用鄰接表來存儲static int N = 510;static int M = 10010;// 存儲所有邊static Node[] e = new Node[M];// 存儲距離起點的距離static int[] d = new int[N];// 備份 d 數組static int[] b = new int[N];static int idx = 1;// 初始化值static final int INF = 0x3f3f3f3f;public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] s = br.readLine().split(" ");int n = Integer.parseInt(s[0]);int m = Integer.parseInt(s[1]);int k = Integer.parseInt(s[2]);for(int i = 1; i <= m; i++){s = br.readLine().split(" ");int x = Integer.parseInt(s[0]);int y = Integer.parseInt(s[1]);int z = Integer.parseInt(s[2]);e[i] = new Node(x, y, z);}bellmanFord(n, m, k);}public static void bellmanFord(int n, int m, int k){Arrays.fill(d, INF);// 起點初始化為 0d[1] = 0;// 最多 k 條邊,循環限制 k 次for(int i = 0; i < k; i++){// 拷貝數組,否則會有串聯問題,導致計算邊的數量不準確b = Arrays.copyOf(d, N);for(int j = 1; j <= m; j++){int x = e[j].x, y = e[j].y, z = e[j].z;d[y] = Math.min(d[y], b[x] + z);}}if(d[n] > INF / 2){System.out.println("impossible");}else{System.out.println(d[n]);}}static class Node{int x, y, z;public Node(int x, int y, int z){this.x = x;this.y = y;this.z = z;}}
}