最短路径

import java.io.*;
import java.util.*;


public class Main {

  static int n;
  static int[] h;
  static int[] e;
  static int[] ne;
  static int idx = 0;
  static int[] w;
  static int m;
  static int[] dis;
  static boolean[] vs;


  public static void add(int x,int y,int val){
    e[idx] = y;
    ne[idx] = h[x];
    w[idx] = val;
    h[x] = idx++;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    String[] line = buf.readLine().split(" ");
    n = Integer.parseInt(line[0]);
    m = Integer.parseInt(line[1]);
    int s = Integer.parseInt(line[2]);
    int t = Integer.parseInt(line[3]);
    h = new int[n + 10];
    e = new int[100010];
    ne = new int[100010];
    w = new int[100010];
    dis = new int[n + 10];
    vs = new boolean[n + 10];

    Arrays.fill(h,-1);

    for (int i = 0; i < m; i++){
      line = buf.readLine().split(" ");
      int x = Integer.parseInt(line[0]);
      int y = Integer.parseInt(line[1]);
      int val = Integer.parseInt(line[2]);
      add(x,y,val);
    }

    int res = dij(s,t);

    System.out.println(res);

  }

  public static int dij(int s,int t){
    Arrays.fill(dis,Integer.MAX_VALUE >> 1);
    dis[s] = 0;
    for (int i = 1; i <= n; i++){
      int node = -1;
      for (int j = 1; j <= n; j++){
        if (!vs[j] && (node == -1 || dis[j] < dis[node])){
          node = j;
        }
      }
      vs[node] = true;
      for (int j = h[node]; j != -1; j = ne[j]){
        int child = e[j];
        if (!vs[child]){
          dis[child] = Math.min(dis[child],dis[node] + w[j]);
        }
      }
    }
    if (dis[t] >= (Integer.MAX_VALUE >> 1)) return -1;
    return dis[t];
  }

}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int m = in.nextInt();
            int start = in.nextInt();
            int end = in.nextInt();
            HashMap<Integer,Node> nodes = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int from = in.nextInt();
                int to = in.nextInt();
                int weight = in.nextInt();
                if(!nodes.containsKey(from)){
                    nodes.put(from,new Node(from));
                }
                if(!nodes.containsKey(to)){
                    nodes.put(to,new Node(to));
                }
                Node fromNode = nodes.get(from);
                Node toNode = nodes.get(to);
                Edge newEdge = new Edge(weight,fromNode,toNode);
                fromNode.nexts.add(toNode);
                fromNode.edges.add(newEdge);
            }
            System.out.println(getShortestPath(nodes,start,end));
        }
        in.close();
    }

    public static int getShortestPath(HashMap<Integer,Node> nodes, int start, int end){
        HashMap<Node,Integer> distanceMap = new HashMap<>();
        distanceMap.put(nodes.get(start),0);
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        while (minNode!=null){
            int distance = distanceMap.get(minNode);
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if(!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance+edge.weight);
                }else {
                    distanceMap.put(toNode,Math.min(distanceMap.get(toNode),distance+edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        }
        return distanceMap.get(nodes.get(end));
    }

    private static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes){
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<Node,Integer> entry : distanceMap.entrySet()){
            Node node = entry.getKey();
            int distance = entry.getValue();
            if(!touchedNodes.contains(node) && distance<minDistance){
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    static class Node{
        int id;
        ArrayList<Node> nexts;
        ArrayList<Edge> edges;

        public Node(int id) {
            this.id = id;
            this.nexts = new ArrayList<>();
            this.edges = new ArrayList<>();
        }
    }

    static class Edge{
        int weight;
        Node from;
        Node to;

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }
}