题目描述

spfa求最短路

JAVA 代码

/*bellman_ford算法对于所有的边都要遍历一遍，
但是对于式子dist[b] = dist[a] + w,dist[b]能更新的条件是dist[a]被更新过，
所以spfa算法就使用一个队列来保存所有被更新过的节点，
每一次都用更新过的节点去更新其它节点。

转自:https://www.acwing.com/activity/content/code/content/176555/
*/

//spfa算法的时间复杂度最最坏为O(n∗mn∗m),一般情况下为O(mm),其中m为边数，n为点数
import java.util.*;
import java.io.*;

class Main{
    static int N = 100010;
    static int[] h = new int[N], e = new int[N], ne =new int[N];
    static int[] w = new int[N], d = new int[N];
    static boolean[] st = new boolean[N];
    static int n,m, idx, INF = 0x3f3f3f3f;


    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(){
        Arrays.fill(d, INF);
        d[1] = 0;
        st[1] = true;

        //声明一个优先队列保存更新过的节点
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;

            for(int i=h[t]; i!=-1;i= ne[i]){
                int j = e[i];
                //如果当前节点可以被更新，就做更新操作，并将该节点加入到队列中 
                if(d[j] > d[t]+ w[i]){
                    d[j] = d[t]+w[i];
                    if(!st[t] ){//如果这个可以更新的节点已经在队列中，就无须再次添加
                        q.offer(j);
                        st[j] =true;
                    }
                }
            }
        }

        if(d[n] > INF/2) return -1;
        return d[n];
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        Arrays.fill(h, -1);

        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
        }

        int t = spfa();
        if(t==-1)System.out.println("impossible");
        else System.out.println(t);
    }
}