반응형
https://www.acmicpc.net/problem/1504
풀이
전형적인 다익스트라 알고리즘 문제.
최단경로 응용 문제로 진행 과정을 자세하게 적어뒀다.
다익스트라에 대해서 처음 접하시는 분은 아래 링크를 먼저 읽어보는 걸 추천한다.
https://sookr5416.tistory.com/160
다익스트라 알고리즘은 한 노드에서 모든 노드 사이의 최단거리를 구할 수 있는 알고리즘이다.
위 문제에서는 특정 노드 2개를 반드시 방문해야된다고 적혀있다.
복잡하게 생각할 것 없다. 다익스트라의 알고리즘을 쪼개서 경로를 찾아주면 된다.
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Node>[] arrList;
public static class Node implements Comparable<Node> {
int e;
int v;
public Node (int e, int v) {
this.e = e;
this.v = v;
}
public int compareTo (Node o) {
return this.v - o.v;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
arrList = new ArrayList[N+1];
for (int i=1; i<=N; i++) {
arrList[i] = new ArrayList<Node>();
}
for (int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
arrList[start].add(new Node(end, value));
arrList[end].add(new Node(start, value));
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
// 1번
long first = 0;
first += Dijkstra(1, v1);
first += Dijkstra(v1, v2);
first += Dijkstra(v2, N);
// 2번
long second = 0;
second += Dijkstra(1, v2);
second += Dijkstra(v2, v1);
second += Dijkstra(v1, N);
if (Math.min(first, second) >= 200000000) System.out.println(-1);
else System.out.println(Math.min(first, second));
}
public static int Dijkstra(int start, int end) {
int[] dp = new int[N+1];
Arrays.fill(dp, 200000000); // 200,000(E의 최대값) * 1,000(c의 최대값) - overflow 방지
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
dp[start] = 0;
while (!pq.isEmpty()) {
Node now = pq.poll();
for (Node n : arrList[now.e]) {
if (dp[n.e] > dp[now.e] + n.v) {
dp[n.e]= dp[now.e] + n.v;
pq.add(new Node(n.e, dp[n.e]));
}
}
}
return dp[end];
}
}
반응형
'알고리즘 > 최소신장트리(MST) & 다익스트라' 카테고리의 다른 글
[백준]JAVA - 1976번: 여행 가자 (0) | 2023.04.20 |
---|---|
[백준]JAVA - 20926번: 얼음 미로 (0) | 2023.03.07 |
[백준]JAVA - 1197번: 최소 스패닝 트리 (0) | 2022.11.07 |
[백준]JAVA - 1753번: 최단 경로 (0) | 2022.10.31 |
[백준]JAVA - 1922번: 네트워크 연결 (0) | 2022.10.24 |