백준 | 14284번. 간선 이어가기 2 - 다익스트라

⬛ 백준 14284번. 간선 이어가기 2 - 다익스트라

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

14284번: 간선 이어가기 2

문제

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

입력

첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주어진다.(2≤n≤5000,1≤m≤100,000)

다음 m줄에는 a,b,c가 주어지는데, 이는 a와 b는 c의 가중치를 가짐을 말한다. (1≤a,b≤n,1≤c≤100,a≠b)

다음 줄에는 두 정점 s,t가 주어진다. (1≤s,t≤n,s≠t)

모든 간선을 연결하면 그래프는 연결 그래프가 됨이 보장된다.

출력

s와 t가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오,

---

💚나의 풀이

• 간단한 다익스트라 문제이다.
• 시작 정점을 S로 하는 distance 배열을 다익스트라로 채운 뒤, distacne[T]의 값을 최종 정답으로 출력하면 된다.

package to_0901_5;

import java.util.*;
import java.util.Scanner;

/*백준 14284번. 간선 이어가기 2 - 다익스트라 문풀 */
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, M, S, T;
	static int[] distance;
	static ArrayList<ArrayList<Edge> > graph;
	static boolean[]visited;
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		distance= new int[N+1];
		visited = new boolean[N+1];
		graph = new ArrayList<>();
		
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		//데이터 입력받기 
		for(int i=0; i<M; 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));
		}
		//S , T 입력 
		S = kb.nextInt(); //시작점 
		T = kb.nextInt();// 종료지점 
		
		//다익스트라 시작 
		Arrays.fill(distance, Integer.MAX_VALUE);
		PriorityQueue<Edge> pQ= new PriorityQueue<>();
		
		//시작점 처리 
		distance[S] = 0;
		pQ.offer(new Edge(S, 0));
		
		while(!pQ.isEmpty()) {
			Edge cur = pQ.poll();
			if(visited[cur.e]) continue;
			visited[cur.e] = true;
			
			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]));
				}
			}
		}
		System.out.println(distance[T]);
	}
}