[백준] 자바 23807 두 단계 최단 경로 3

문제

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(undirected graph), 도로의 길이가 간선의 가중치이다. 출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 세 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 구해서 우리 서준이를 도와주자.

입력

첫째 줄에 정점의 수 N(10 ≤ N ≤ 100,000), 간선의 수 M(10 ≤ M ≤ 300,000)이 주어진다.

다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 1,000,000)

다음 줄에 X Z가 주어진다. (1 ≤ X, Z ≤ N, X ≠ Z)

다음 줄에 P가 주어진다. (3 ≤ P ≤ min(100, N - 3))

다음 줄에 P개의 서로 다른 중간 정점 Y(1 ≤ Y ≤ N, X ≠ Y ≠ Z)가 빈칸을 사이에 두고 주어진다.

출력

출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 세 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 출력한다. 도착 정점 Z에 도착할 수 없는 경우 -1을 출력한다.

---

테스트 케이스

 

입력 1

5 1
1 5 1
1 5
3
2 3 4

출력 1

-1

 

입력 2

12 19
1 2 1
1 3 1
1 4 10
1 5 10
2 3 1
2 6 10
3 4 1
3 7 1
4 5 10
4 8 10
5 9 1
6 7 1
6 10 1
7 8 1
7 10 10
8 11 10
9 11 1
10 12 1
11 12 1
1 12
4
2 4 5 7

출력 2

8

 

---

접근

다익스트라 문제 입니다.

시작점에서 다익스트라를 돌고

받은 P값들을 모두 다익스트라를 돌아서,

시작점 => P1 => P2 => P3 => 도착점

 

(다익스트라로 찾아낸 값을 통해 시작점 P1이동,

P1에서 P2까지 다익스트라로 찾아낸 값으로 이동,

P2에서 P3까지 다익스트라로 찾아낸 값으로 이동,

P3에서 도착점까지 다익스트라로 찾아낸 값으로 이동)

 

이를 반복합니다.

시작점 => P1 => P3 => P2  => 도착점

시작점 => P2 => P1 => P3 => 도착점

...

P의 점중 3개를 골라서 최소값을 찾아냅니다.(순열)

---

코드

import java.util.*;
import java.io.*;

class Vertex implements Comparable<Vertex> {
	int no;
	long dis;

	public Vertex(int no, long dis) {
		this.no = no;
		this.dis = dis;
	}

	@Override
	public int compareTo(Vertex o) {
		// TODO Auto-generated method stub
		if(this.dis < o.dis) return -1;
		else if(this.dis > o.dis) return 1;
		else return 0;
	}
}

public class Main {
	static int N, M, p, last;
	static long distance[][];
	static boolean visit[];
	static int num[];
	static long min = 999876454321L;
	public static void permu(int arr[], int cnt) {
		if(cnt == 3) {
			long temp = distance[0][arr[num[0]]] + distance[num[0]][arr[num[1]]] + distance[num[1]][arr[num[2]]] + distance[num[2]][last];
			min = Math.min(min, temp);
			return;
		}
		
		for(int i=1; i<=p; i++) {
			if(!visit[i]) {
				visit[i] = true;
				num[cnt] = i;
				permu(arr,cnt+1);
				visit[i] = false;
			}
		}
	}
	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());
		M = Integer.parseInt(st.nextToken());
		ArrayList<Vertex> list[] = new ArrayList[N];
		//연결관계 정리
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken())-1;
			int end = Integer.parseInt(st.nextToken())-1;
			int value = Integer.parseInt(st.nextToken());
			list[start].add(new Vertex(end, value));
			list[end].add(new Vertex(start, value));
		}
		//시작 끝 지점 입력
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken())-1;
		last = Integer.parseInt(st.nextToken())-1;
		p = Integer.parseInt(br.readLine());
		
		//순열을 위한
		visit = new boolean[p+1];
		num = new int[3];
		
		//거치는 점들
		int arr[] = new int[p + 1];
		st = new StringTokenizer(br.readLine());
		//시작지점은 0
		arr[0] = start;
		for (int i = 1; i < p+1; i++) {
			arr[i] = Integer.parseInt(st.nextToken())-1;
		}
		//다익스트라 p+1개
		distance = new long[p+1][N];
		for (int i = 0; i <p+1; i++) {
			Arrays.fill(distance[i], 999876454321L);
			distance[i][arr[i]]= 0;
		}
		//다익스트라 돌기
		for (int i = 0; i < p + 1; i++) {
			PriorityQueue<Vertex> pq = new PriorityQueue<>();
			pq.add(new Vertex(arr[i], 0));
			while (!pq.isEmpty()) {
				Vertex cur = pq.poll();
				if (distance[i][cur.no] < cur.dis)
					continue;
				for (int j = 0; j < list[cur.no].size(); j++) {
					Vertex next = list[cur.no].get(j);
					if (distance[i][next.no] > cur.dis + next.dis) {
						distance[i][next.no] = cur.dis + next.dis;
						pq.add(new Vertex(next.no, distance[i][next.no]));
					}
				}
			}
		}
		//순열
		permu(arr,0);
		
		if(min == 999876454321L) min = -1;
		System.out.println(min);
		br.close();
	}
}

---

주의

LONG값 써야함!!