특정한 최단 경로
https://www.acmicpc.net/problem/1504
문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
문제 풀이 방법 및 해설
이번 문제는 정말 많은 어려움을 겪었었다. 바로 문제 해설로 들어가보자.
문제에서는 시작점이 무조건 1, 도착점이 무조건 N으로 되어있으며 경유해야할 정점이 2개 주어진다. 그래서 케이스로만 확인해보면 다음과 같다.
- 1 -> V1 -> V2 -> N
- 1 -> V2 -> V2 -> N
그리고 다익스트라 알고리즘을 통해 해당 정점에서 다음 정점까지의 최소거리를 구하면 된다.
정점 까지의 최대거리는 2억이기 때문에 모든 값을 2억으로 초기화를 해준 후 1번의 경우와 2번의 경우 모두를 계산을 한다.
1번 계산이나 2번 계산의 결과값이 기존에 설정한 2억이상이면 갈 수 없는 길이 존재하는 것 이기 때문에 조건을 처리해주면 된다!
풀이 코드
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 {
public static class Node implements Comparable<Node>{
int idx, cost;
public Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int[][] answer = new int[N+1][N+1];
ArrayList<Node>[] lst = new ArrayList[N+1];
for(int i = 1 ; i <= N ; i++){
Arrays.fill(answer[i], 200000000);
lst[i] = new ArrayList<>();
}
for(int i = 0 ; i < E ; i++){
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
lst[s].add(new Node(e, c));
lst[e].add(new Node(s, c));
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(v1);
list.add(v2);
list.add(N);
for(int i = 0 ; i <list.size() ; i++){
int idx = list.get(i);
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(idx, 0));
answer[idx][idx] = 0;
while(!pq.isEmpty()){
Node cur = pq.poll();
if(cur.cost != answer[idx][cur.idx]) continue;
for(Node next : lst[cur.idx]){
if(answer[idx][next.idx] > answer[idx][cur.idx] + next.cost){
answer[idx][next.idx] = answer[idx][cur.idx] + next.cost;
pq.offer(new Node(next.idx, answer[idx][next.idx]));
}
}
}
}
long sum1 = answer[1][v1] + answer[v1][v2] + answer[v2][N];
long sum2 = answer[1][v2] + answer[v2][v1] + answer[v1][N];
if(sum1 >= 200000000 && sum2 >= 200000000){
System.out.println(-1);
}else{
System.out.println(Math.min(sum1, sum2));
}
}
}
