题目描述

基于SPFA算法的基础上修改而来，下面是链接：
SPFA算法

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int n, m, idx;
    static int M = 300010, N = 100010;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int[] dist = new int[N];
    static boolean[]st = new boolean[N];
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = reader.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        Arrays.fill(h, -1);
        while(m-- > 0){
            int a, b, c;
            temp = reader.readLine().split(" ");
            a = Integer.parseInt(temp[0]);
            b = Integer.parseInt(temp[1]);
            c = Integer.parseInt(temp[2]);
            add(a,b,c);
            add(b,a,c);
        }
        m = Integer.parseInt(reader.readLine());
        while(m-- > 0){
            int v = Integer.parseInt(reader.readLine());
            //插入一条到商店距离为0的中心点
            add(0,v,0);
        }

        spfa();

        m = Integer.parseInt(reader.readLine());
        while(m-- > 0){
            int v = Integer.parseInt(reader.readLine());
            //最后只需要依次输出中心点到所求点的距离即为该店到商店的最短距离
            writer.write(dist[v]+"\n");
        }
        writer.flush();


    }
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static void spfa(){
        Arrays.fill(dist, 0x7f7f7f7f);
        Deque<Integer> queue = new ArrayDeque<>();
        //这里使用了一个中心点0，因此开始的点是0
        dist[0] = 0;
        st[0] = true;
        queue.addLast(0);

        while(!queue.isEmpty()){
            int t = queue.poll();
            st[t] = false;

            for (int i = h[t]; i != -1 ; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t]+w[i]){
                    dist[j] = dist[t] + w[i];
                    if (!st[j]){
                        st[j] = true;
                        queue.addLast(j);
                    }
                }
            }
        }
    }
}