給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數，
請你求出1號點到n號點的最短距離，如果無法從1號點走到n號點，則輸出impossible，
資料保證不存在負權回路，
輸入格式
第一行包含整數n和m，
接下來m行每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z，
輸出格式
輸出一個整數，表示1號點到n號點的最短距離，
如果路徑不存在，則輸出”impossible”，
資料范圍
1≤n,m≤1051≤n,m≤105,
圖中涉及邊長絕對值均不超過10000，
輸入樣例：
3 3
1 2 5
2 3 -3
1 3 4
輸出樣例：
2
對Bellman-ford演算法的佇列優化
代碼：//鄰接表存盤 //n=1e5，不能用鄰接表 import java.util.ArrayDeque; import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=100005, INF=0x3f3f3f3f; static int h[]=new int[N]; static int e[]=new int[N]; static int ne[]=new int[N]; static int w[]=new int[N]; static int dis[]=new int[N]; static boolean vis[]=new boolean[N]; static int n,m,idx; static void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } static int spfa(){ ArrayDeque<Integer> q = new ArrayDeque<Integer>(); Arrays.fill(dis, INF); dis[1]=0; q.offer(1); vis[1]=true;//vis陣串列示當前點是否在佇列中 while(!q.isEmpty()){ int t=q.poll(); vis[t]=false;//不在佇列中，置為false for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j]>dis[t]+w[i]){ dis[j]=dis[t]+w[i]; if(!vis[j]){ vis[j]=true; q.offer(j); } } } } if(dis[n]==INF) return -1; else return dis[n]; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); Arrays.fill(h, -1); while(m-->0){ int a=scan.nextInt(); int b=scan.nextInt(); int c=scan.nextInt(); add(a,b,c); } int t=spfa(); if(t==-1) System.out.println("impossible"); else System.out.println(t); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/95238.html
標籤：其他
上一篇：853. 有邊數限制的最短路（Bellman-ford演算法模板）
下一篇：852. spfa判斷負環