BOJ - 최소비용 구하기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

• 최단 경로 문제이다.
  • 다익스트라 알고리즘을 연습 할 수 있는 좋은 문제이다.

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws Exception {
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        // 도시 수
        Node[] nodes = new Node[N + 1];
        for (int i = 1; i <= N; i++) {
            nodes[i] = new Node(i);
        }

        // 버스 간선 수
        for (int i = 0; i < M; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();

            Edge edge = new Edge(nodes[u], nodes[v], w);
            nodes[u].edges.add(edge);
        }

        // 출발 지 목적지
        int origin = scanner.nextInt();
        int dest = scanner.nextInt();

        boolean[] visit = new boolean[N + 1];
        int[] distance = new int[N + 1];

        PriorityQueue<State> queue = new PriorityQueue<>();
        queue.add(new State(nodes[origin], 0));

        while (!queue.isEmpty()) {
            State node = queue.poll();
            if (visit[node.currentNode.index] == true) continue;
            visit[node.currentNode.index] = true;
            distance[node.currentNode.index] = node.totalWeight;

            if(node.currentNode.index == dest) {
                System.out.println(node.totalWeight);
                System.exit(0);
            }

            for (Edge edge : node.currentNode.edges) {
                Node next = edge.dest;
                if (visit[next.index] == true) continue;
                queue.add(new State(next, node.totalWeight + edge.weight));
            }
        }
    }
}

class Node {
    public int index;
    public ArrayList<Edge> edges;

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

class State implements Comparable<State> {
    public Node currentNode;
    public int totalWeight;

    public State(Node currentNode, int totalWeight) {
        this.currentNode = currentNode;
        this.totalWeight = totalWeight;
    }

    @Override
    public int compareTo(State other) {
        return this.totalWeight - other.totalWeight;
    }
}

class Edge {
    public Node origin;
    public Node dest;
    public int weight;

    public Edge(Node origin, Node dest, int weight) {
        this.origin = origin;
        this.dest = dest;
        this.weight = weight;
    }
}