迪杰斯特拉支持边重复

题目链接

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
/**
 * 表示图：邻接表、邻接矩阵
 * 没有权值为负数的边，单元最短路径，一定规定出发点，计算出该点到其他点的最短路径
 */
public class 单源最短路径 {
    static class Node{
        public int from;
        public int to;
        public int weight;
        public Node(int from,int to,int weight){
            this.from=from;
            this.to=to;
            this.weight=weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return from == node.from && to == node.to;
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }
    }
    static int n,m,start;
    static ArrayList<Node>[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st=new StreamTokenizer(br);
        st.nextToken();n=(int)st.nval;
        st.nextToken();m=(int)st.nval;
        st.nextToken();start=(int)st.nval;
        graph=new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            st.nextToken();int from=(int)st.nval;
            st.nextToken();int to=(int)st.nval;
            st.nextToken();int weight=(int)st.nval;
            Node node=new Node(from,to,weight);
            if(graph[from].contains(node)){
                if(graph[from].get(graph[from].indexOf(node)).weight>weight){
                    graph[from].remove(node);
                    graph[from].add(node);
                }
            }else{
                graph[from].add(node);
            }
        }
        int[] dis=dijkstra(start);
        for(int i=1;i<=n;i++){
            System.out.print(dis[i]+" ");
        }
    }

    private static int[] dijkstra(int start) {
        boolean[] visited=new boolean[n+1];
        Arrays.fill(visited,false);
        visited[start]=true;
        int[] dist=new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        for(Node node:graph[start]){
            dist[node.to]=node.weight;
        }
        dist[start]=0;
        for(int i=1;i<=n;i++){
            int min=Integer.MAX_VALUE;
            int point=-1;
            for(int j=1;j<=n;j++){
                if(!visited[j]&&dist[j]<min){
                    point=j;
                    min=dist[j];
                }
            }
            if(point==-1){
                return dist;
            }
            visited[point]=true;
            for(Node node:graph[point]){
                dist[node.to]=Math.min(dist[node.to],dist[point]+node.weight);
            }
        }
        return dist;
    }
}