给定一个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); } }