蓝桥杯刷题记录之蓝桥王国

只是记录

这题用迪杰斯特拉来就行，我写的是堆优化版本

import java.util.*;

public class Main{
    static Scanner s = new Scanner(System.in);
    static int n,m,startPoint=1;
    static List<Edge>[] table;//邻接表,因为是稀疏图
    static long[] dist;
    static boolean[] used;
    public static void main(String[] args) {
        n = s.nextInt();
        m = s.nextInt();
        used = new boolean[n+1];
        dist = new long[n+1];
        table = new List[n+1];
        for(int i=0;i<=n;i++)
            table[i] = new ArrayList<>();
        for(int i=0;i<m;i++){
            int start = s.nextInt();
            int end = s.nextInt();
            long distance = s.nextLong();
            table[start].add(new Edge(end,distance));
        }
        dijkstra();
        for(int i=1;i<=n;i++){
            System.out.print(dist[i]==Long.MAX_VALUE?"-1 ":dist[i]+" ");
        }
        s.close();
    }
    static void dijkstra(){
        Arrays.fill(dist,Long.MAX_VALUE);
        dist[startPoint]=0;
        PriorityQueue<Edge> pq = new PriorityQueue<>((x,y)->x.distance.compareTo(y.distance));
        pq.add(new Edge(startPoint,0));
        while (!pq.isEmpty()){
            Edge poll = pq.poll();
            int t = poll.end;
            if(used[t])
                continue;
            used[t] = true;
            for(Edge item: table[t]){
                int vertex  = item.end;
                long distance = item.distance;
                if(!used[vertex] && dist[vertex] > dist[t]+distance){
                    dist[vertex] = dist[t]+distance;
                    pq.add(new Edge(vertex,dist[vertex]));
                }
            }
        }
    }
}
class Edge{
    int end;// 终点
    Long distance;//距离
    public Edge(int end,long distance){
        this.end = end;
        this.distance = distance;
    }
}