백준 | 12834번. 주간 미팅 - 다익스트라

⬛ 백준 12834번. 주간 미팅 - 다익스트라

https://www.acmicpc.net/problem/12834

12834번: 주간 미팅

문제

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

---

💚나의 풀이

• 각 팀원의 집 위치를 시작위치로 하고 끝점이 A, B가 되도록 다익스트라를 호출하여 문제를 풀었다.
• 예를 들어 예제에서 팀원 2명에 대한 각각의 위치는 2번과 4번이다.

(1) (2번 → A 최단 거리) + (2번 → B 최단 거리)

(2) (4번 → A 최단 거리) + (4번 → B 최단 거리)

• 저 상태에서 (1) + (2) 를 해주면 팀원 모든 사람의 최단 거리 합이 된다.
• 그리고 도달할 수 없을 경우 Integer.MAX 값을 지니고 있을 것이므로 -1로 바꿔서 합을 구해줄 것을 주의

package to_0902_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/*12834번. 주간 미팅 - 다익스트라 */
class Edge implements Comparable<Edge>{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val =val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;
	}
}
public class Main {
	static int N, V, E; //팀원, 정점 , 간선 
	static int A, B; //Kist, 씨아푸드 위치
	static int[] team;//N명의 팀원들 위치 
	static ArrayList<ArrayList<Edge>> graph;
	//다익스트라 
	static int dijkstra(int st, int e) { //시작점과 끝점에 대한 최단거리 리턴 
		boolean[] visited= new boolean[V+1];
		int[] distance = new int[V+1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		//시작점 초기화
		distance[st] = 0;
		pQ.offer(new Edge(st, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			//도착점 발견하면 
			if(cur.e == e) return distance[cur.e];//여기서 리턴
			
			for(Edge nx : graph.get(cur.e)) {
				if(!visited[nx.e] && distance[nx.e] > distance[cur.e] + nx.val ) {
					distance[nx.e] = distance[cur.e] + nx.val;
					pQ.offer(new Edge(nx.e, distance[nx.e]));
				}
			}
		}
		return distance[e];//도착점 좌표 보낼 건데 
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		V = kb.nextInt();
		E = kb.nextInt();
		
		A = kb.nextInt();
		B = kb.nextInt();
		
		team = new int[N];
		for(int i=0; i<N; i++) {
			team[i] = kb.nextInt();//팀원 집 위치 
		}
		
		graph = new ArrayList<>();
		for(int i=0; i<=V; i++) {//정점은 V개 
			graph.add(new ArrayList<>());
		}
		
		//데이터 입력
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int c = kb.nextInt();
			//양방향 
			graph.get(a).add(new Edge(b, c));
			graph.get(b).add(new Edge(a, c));
		}
		
		int sum =0;
		//호출 -> 각 팀원별
		for(int i=0; i<N; i++) {
			//현재 팀원 -> kist 위치 
			int a = dijkstra(team[i], A);
			//현재 팀원 - 씨앗 푸드 거리 
			int b = dijkstra(team[i] , B);
			
			if(a==Integer.MAX_VALUE) {
				a = -1;//고쳐주고
			}else if(b == Integer.MAX_VALUE) {
				b = -1;
			}
			
			sum += (a+b);//각각의 팀원별 거리 합 구하기
		}
		
		System.out.println(sum);
		
	}
}