간선 이어가기2 - 14284번

---

풀이 방법

처음에 문제가 잘 이해되지 않았다.

"간선의 순서를 조정할때 최솟값을 구하시오" 이 말은 그냥 최소 경로를 구하라는 말과 같다.

그래서 다익스트라를 이용해서 풀이했다.

 

 

내 코드

package com.company;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s, t;
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] graph = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            Arrays.fill(graph[i], 1000000);
            graph[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            graph[x][y] = z;
            graph[y][x] = z;
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (int i = 1; i <= n; i++) {
            pq.add(new Node(i, graph[s][i]));
        }

        boolean[] visited = new boolean[n + 1];

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (node.b == t) {
                System.out.println(graph[s][node.b]);
                break;
            }
            visited[node.b] = true;

            for (int i = 1; i <= n; i++) {
                if (!visited[i] && graph[s][i] > node.c + graph[node.b][i]) {
                    graph[s][i] = node.c + graph[node.b][i];
                    pq.add(new Node(i, graph[s][i]));
                }
            }

        }
    }
}

class Node implements Comparable<Node> {
    int b;
    int c;

    public Node(int b, int c) {
        this.b = b;
        this.c = c;
    }

    @Override
    public int compareTo(Node o) {
        return c - o.c;
    }
}