[Gold V] 간선 이어가기 2 - 14284
성능 요약
메모리: 43776 KB, 시간: 356 ms
분류
데이크스트라, 그래프 이론, 최단 경로
제출 일자
2024년 6월 18일 20:28:14
문제 설명
정점 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가 연결되는 시점의 간선의 가중치 합의 최솟값을 출력하시오,
접근 방법
1. 모든 길이 이어졌다는 가정하에 S에서 E로 갈 수 있는 최적의 거리를 계산해준다.(다익스트라 알고리즘)
풀이코드
import java.util.*;
import java.io.*;
/**
* 문제 : BOJ_14284_간선 이어가기 2
* 메모리: 43776KB
* 시간: 356ms
* 접근 방법
* 1. 모든 길이 이어져있다는 가정하에 s에서 e로 갈 수 있는 최적의 거리를 계산해준다.(다익스트라)
*/
public class Main {
// 간선(Edge)
static class Node{
int idx;
int weight;
Node next;
public Node(int idx, int weight, Node next) {
this.idx = idx;
this.weight = weight;
this.next = next;
}
}
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 M = Integer.parseInt(st.nextToken());
// Input
Node[] graph = new Node[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a] = new Node(b, c, graph[a]);
graph[b] = new Node(a, c, graph[b]);
} // Input End
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
// 최대값은 500_000
int[] cost = new int[N + 1];
Arrays.fill(cost, 500_001);
Queue<Node> q = new LinkedList<>();
q.add(new Node(s, 0, null));
cost[s] = 0;
while (!q.isEmpty()) {
Node cur = q.poll();
if (cost[cur.idx] < cur.weight) {
continue;
}
for (Node tmp = graph[cur.idx]; tmp != null; tmp = tmp.next) {
if (cost[tmp.idx] > tmp.weight + cost[cur.idx]) {
cost[tmp.idx] = tmp.weight + cost[cur.idx];
q.add(new Node(tmp.idx, cost[tmp.idx], null));
}
}
}
System.out.println(cost[e]);
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 18513번 : 샘터 Gold4(골드4) - JAVA[자바] (0) | 2024.06.19 |
---|---|
[백준] 14391번 : 종이 조각 Gold3(골드3) - JAVA[자바] (0) | 2024.06.19 |
[백준] 2374번 : 같은 수로 만들기 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |
[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바] (1) | 2024.06.18 |
[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바] (0) | 2024.06.18 |