题目描述

简单题不配拥有题解吗，还有这个我是用java写的，依旧是使用优先队列
对java不太友好的是————因为数据量过大，所以输入要使用BufferedReader,这样才能不超时。
担心有跟我一样找不到问题莫名其妙的小伙伴，因为超时在疯狂找原因。
还有第一次弄，这个格式有点问题，比较那个方法comparator命名为com它是[HTML_REMOVED]类型的，它自动替换了别的我也不知道为什么==

样例

//1488 最短距离

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
static class Edge{
int b;
int c;
public Edge(int b,int c){
this.b=b;
this.c=c;
}
}
static Comparator[HTML_REMOVED] com=new Comparator[HTML_REMOVED]() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.c>o2.c?1:-1;
}

};
public static void dijk(List<List<Edge>> g,int[] dis,boolean[] std) {
    Queue<Edge> shop=new PriorityQueue<>(com);
    shop.offer(new Edge(0,0));

    while(!shop.isEmpty()) {        
        while(!shop.isEmpty()&&std[shop.peek().b]==true) {
            shop.poll();
        }
        if(shop.isEmpty())
            break;
        int t=shop.poll().b;
        std[t]=true;

        for(int i=0;i<g.get(t).size();i++) {
            if(std[g.get(t).get(i).b]==false&&dis[g.get(t).get(i).b]>dis[t]+g.get(t).get(i).c) {
                dis[g.get(t).get(i).b]=dis[t]+g.get(t).get(i).c;
                shop.add(new Edge(g.get(t).get(i).b,dis[g.get(t).get(i).b]));
            }
        }

    }

}
public static void main(String[] args) throws IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));     
    //Scanner s =new Scanner(System.in);
    String[] aaa=br.readLine().split(" ");
    int n=Integer.valueOf(aaa[0]);  //n个村
    int m=Integer.valueOf(aaa[1]);  //m个无向路
    List<List<Edge>> g=new ArrayList<>();
    for(int i=0;i<n+1;i++) {
        g.add(new ArrayList<>());//村子(1~n)+1
    }
    int[] dis=new int[n+1];
    Arrays.fill(dis, Integer.MAX_VALUE);
    dis[0]=0;
    boolean[] std=new boolean[n+1];

    for(int i=0;i<m;i++) {
        String[] bb=br.readLine().split(" ");
        int a=Integer.valueOf(bb[0]);
        int b=Integer.valueOf(bb[1]);
        int c=Integer.valueOf(bb[2]);
        g.get(a).add(new Edge(b,c));
        g.get(b).add(new Edge(a,c));
    }
    int k=Integer.valueOf(br.readLine());//商店个数
    for(int i=0;i<k;i++) {
        int shop=Integer.valueOf(br.readLine());
        g.get(0).add(new Edge(shop,0));
        g.get(shop).add(new Edge(0,0));
    }
    dijk(g,dis,std);
    int q=Integer.valueOf(br.readLine());//q个询问
    for(int i=0;i<q;i++) {
        int q0=Integer.valueOf(br.readLine());
        System.out.println(dis[q0]);
    }


}

}