풀이 방법
처음에 문제가 잘 이해되지 않았다.
"간선의 순서를 조정할때 최솟값을 구하시오" 이 말은 그냥 최소 경로를 구하라는 말과 같다.
그래서 다익스트라를 이용해서 풀이했다.
내 코드
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;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
불 - 5427번 (0) | 2022.01.24 |
---|---|
월드컵 - 6987번 (0) | 2022.01.24 |
백양로 브레이크 - 11562번 (0) | 2022.01.19 |
회문 - 17609번 (0) | 2021.12.30 |
해킹 -10282번 (0) | 2021.12.29 |