[BOJ] 1504. 특정한 최단경로
문제
풀이
이 문제는 1(시작정점)->N 까지의 최소비용을 구하는 다익스트라 알고리즘을 응용한 문제였다.
중간에 v1,v2 정점을 무조건 거치기 위해서 1->N의 경로를
(1) 1->v1->v2->N
(2) 1->v2->v1->N
쪼개서 두 가지 방식 모두 구하고 그 중 작은 값을 택하도록 했다.
만약 v1,v2를 거치고 N까지 가는 방법이 존재하지 않는 다면 -1을 리턴하도록 했다.
JAVA코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 백준1504_특정한최단경로 {
static int N, E; // 정점의 개수, 간선의 개수
static int v1, v2; // 반드시 거쳐야 하는 두 개의서로 다른 정점
static ArrayList<ArrayList<Node>> adjList = new ArrayList<>();
static int[] dist;
static boolean[] visited;
static int INF = 200000000;
static class Node implements Comparable<Node> {
int idx, weight;
public Node(int idx, int weight) {
super();
this.idx = idx;
this.weight = weight;
}
@Override
public int compareTo(Node arg0) {
return Integer.compare(this.weight, arg0.weight); // weight를 기준으로 정렬, 오름차순
}
}
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());
E = Integer.parseInt(st.nextToken());
for (int i = 0; i <N+1; i++) {
adjList.add(new ArrayList<Node>());
}
dist = new int[N + 1];
visited = new boolean[N + 1];
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList.get(from).add(new Node(to, weight));
adjList.get(to).add(new Node(from, weight));
}
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
int res1 = 0;
res1 += dijkstra(1, v1);
res1 += dijkstra(v1, v2);
res1 += dijkstra(v2, N);
int res2 = 0;
res2 += dijkstra(1, v2);
res2 += dijkstra(v2, v1);
res2 += dijkstra(v1, N);
int ans = 0;
if (res1 >= INF && res2 >= INF)
ans = -1;
else {
ans = res1 < res2 ? res1 : res2;
}
System.out.println(ans);
}
public static int dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<Node>();
Arrays.fill(dist, INF); // dist 배열 초기화
Arrays.fill(visited, false); // visited 배열 초기화
pq.offer(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node current = pq.poll();
if(visited[current.idx]) continue;
visited[current.idx] = true;
for (Node next : adjList.get(current.idx)) {
if (!visited[next.idx] && dist[next.idx] > dist[current.idx] + next.weight) {
dist[next.idx] = dist[current.idx] + next.weight;
pq.offer(new Node(next.idx, dist[next.idx]));
}
}
}
return dist[end];
}
}
Author And Source
이 문제에 관하여([BOJ] 1504. 특정한 최단경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw7000/BOJ-1504.-특정한-최단경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)