給定一個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
代碼：//可能出現負權回路，所以最短路徑不一定存在 import java.util.Arrays; import java.util.Scanner; class Node{ int a; int b; int w; } public class Main{ static final int N=505, INF=(int)1e9+5; static int n,m,k; static int dis[]=new int[N]; static int backup[]=new int[N];//使用上一次更新的狀態，避免串聯更新，eg：更新過1到2距離，然后利用另一個條件又更新了一遍 static Node node[]=new Node[10005]; static int bellman_ford(){ Arrays.fill(dis, INF); dis[1]=0; for(int i=1;i<=k;i++){//k次更新，說明a到b最多不超過k條邊 backup=Arrays.copyOf(dis, n+1); for(int j=0;j<m;j++){//更新每條邊 int a=node[j].a; int b=node[j].b; int w=node[j].w; dis[b]=Math.min(dis[b],backup[a]+w);//松弛操作 } } if(dis[n]>INF/2) return -1;//因為可能出現負權邊，所以就算dis[n]不可達，但可能出現dis[n]<INF else return dis[n]; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); k=scan.nextInt(); for(int i=0;i<m;i++){ node[i]=new Node(); node[i].a=scan.nextInt(); node[i].b=scan.nextInt(); node[i].w=scan.nextInt(); } int ans=bellman_ford(); if(ans==-1) System.out.println("impossible"); else System.out.println(ans); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95236.html
標籤：其他