Life Engineering
[BOJ 1504] 특정한 최단 경로 (Java) 본문
https://www.acmicpc.net/problem/1504
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 Main_BOJ_1504 {
static class Node implements Comparable<Node>{
int id, cost;
Node(int dest, int cost){
this.id=dest;
this.cost=cost;
}
@Override
public int compareTo(Node o) {
return this.cost-o.cost;
}
}
static int N, E;
static ArrayList<ArrayList<Node>> li=new ArrayList<>();
static long answer=Long.MAX_VALUE;
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++) {
li.add(new ArrayList<>());
}
for (int i = 0; i < E; i++) {
st=new StringTokenizer(br.readLine());
int a=Integer.parseInt(st.nextToken());
int b=Integer.parseInt(st.nextToken());
int c=Integer.parseInt(st.nextToken());
li.get(a).add(new Node(b,c));
li.get(b).add(new Node(a,c));
}
st=new StringTokenizer(br.readLine());
int v1=Integer.parseInt(st.nextToken());
int v2=Integer.parseInt(st.nextToken());
process(v1, v2);
if (answer!=Long.MAX_VALUE) {
System.out.println(answer);
}
else {
System.out.println(-1);
}
}
private static void process(int v1, int v2) {
long sum1=0, sum2=0;
sum1=(dijkstra(1,v1)+dijkstra(v1, v2)+dijkstra(v2, N));
sum2=(dijkstra(1,v2)+dijkstra(v2, v1)+dijkstra(v1, N));
if (sum1<Integer.MAX_VALUE || sum2<Integer.MAX_VALUE) {
answer=Math.min(sum1, sum2);
}
}
private static long dijkstra(int start, int dest) {
int[] dist=new int[N+1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start]=0;
PriorityQueue<Node> pq=new PriorityQueue<>();
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node now=pq.poll();
if (dist[now.id]<now.cost) continue;
for (int i=0; i<li.get(now.id).size(); i++) {
Node neighbor=li.get(now.id).get(i);
if (dist[neighbor.id]>now.cost+neighbor.cost) {
dist[neighbor.id]=now.cost+neighbor.cost;
pq.add(new Node(neighbor.id, dist[neighbor.id]));
}
}
}
return dist[dest];
}
}
다익스트라를 이용하는 코드.
난 6번 돌렸으나..(바보같은 선택), 3번만 돌려도 OK 다.
다익스트라는 출발지 고정일 때 쓴다.
즉, 1->v1->v2->N, 1->v2->v1->N 이렇게 갈 수 있는 2가지 경우의 수가 있다.
1번에서 출발하는 경우(1->v1, 1->v2 일 때 사용 가능)
v1에서 출발하는 경우(v1->v2, v1->N 일 때 사용가능)
v2에서 출발하는 경우(v2->N, v2->v1 일 때 사용가능)
이 3가지의 다익스트라를 구해줘서 최솟값을 구하면 된다.
주의할 점은, 경로가 없는 case가 나올 경우 Integer.MAX_VALUE 가 나올 것이므로, 두 경로 합이 모두 이 이상이 되면 -1을 출력해야 한다.
다익스트라: 출발지 고정임을 기억하고 풀것.
'Problem Solving' 카테고리의 다른 글
[BOJ 20055] 컨베이어 벨트 위의 로봇 (Java) (0) | 2022.03.30 |
---|---|
[BOJ 2636] 치즈 (Java) (0) | 2022.03.30 |
[프로그래머스] 길 찾기 게임 (Java) (0) | 2022.03.25 |
[BOJ 2133] 타일 채우기 (Java) (0) | 2022.03.25 |
[프로그래머스] 불량 사용자 (Java) (0) | 2022.03.24 |