๋ฌธ์
N๊ฐ์ ๋์๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์์ ๋์ฐฉํ๋ M๊ฐ์ ๋ฒ์ค๊ฐ ์๋ค. ์ฐ๋ฆฌ๋ A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ๋ฒ์ค ๋น์ฉ์ ์ต์ํ ์ํค๋ ค๊ณ ํ๋ค. A๋ฒ์งธ ๋์์์ B๋ฒ์งธ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ์ต์๋น์ฉ์ ์ถ๋ ฅํ์ฌ๋ผ. ๋์์ ๋ฒํธ๋ 1๋ถํฐ N๊น์ง์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ M(1 ≤ M ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ ์งธ ์ค๋ถํฐ M+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ ๋ฒ์ค์ ์ถ๋ฐ ๋์์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ๊ทธ ๋ค์์๋ ๋์ฐฉ์ง์ ๋์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๊ณ ๋ ๊ทธ ๋ฒ์ค ๋น์ฉ์ด ์ฃผ์ด์ง๋ค. ๋ฒ์ค ๋น์ฉ์ 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์์ ์ ์์ด๋ค. ๊ทธ๋ฆฌ๊ณ M+3์งธ ์ค์๋ ์ฐ๋ฆฌ๊ฐ ๊ตฌํ๊ณ ์ ํ๋ ๊ตฌ๊ฐ ์ถ๋ฐ์ ์ ๋์๋ฒํธ์ ๋์ฐฉ์ ์ ๋์๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ถ๋ฐ์ ์์ ๋์ฐฉ์ ์ ๊ฐ ์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์ถ๋ฐ ๋์์์ ๋์ฐฉ ๋์๊น์ง ๊ฐ๋๋ฐ ๋๋ ์ต์ ๋น์ฉ์ ์ถ๋ ฅํ๋ค.
ํ์ด
ํน์ ๋ ธ๋์์ ๋ค๋ฅธ ๋ ธ๋๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ๊ธฐ ๋๋ฌธ์ ๋ค์ต์คํธ๋ผ๋ฅผ ๋ ์ฌ๋ฆด ์ ์์์ต๋๋ค. ํ์ด๋ ์๋์ ๊ฐ์ต๋๋ค.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static boolean[] visited;
static int[] distance;
static final int MAX = Integer.MAX_VALUE;
static List<Node>[] nodes;
public static void main(String[] args) throws Exception {
n = input.integer();
m = input.integer();
nodes = new ArrayList[n + 1];
distance = new int[n + 1];
visited = new boolean[n + 1];
for (int i = 1; i < n + 1; i++) {
nodes[i] = new ArrayList<>();
distance[i] = MAX;
}
for (int i = 0; i < m; i++) {
int from = input.integer();
int to = input.integer();
int cost = input.integer();
nodes[from].add(new Node(to, cost));
}
int start = input.integer();
int destination = input.integer();
dijkstra(start);
System.out.println(distance[destination]);
}
private static void dijkstra(int start) {
Queue<Node> queue = new PriorityQueue<>();
queue.add(new Node(start, 0));
distance[start] = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
if (visited[node.to]) continue;
visited[node.to] = true;
for (Node next : nodes[node.to]) {
if (distance[next.to] >= distance[node.to] + next.cost) {
distance[next.to] = distance[node.to] + next.cost;
queue.add(new Node(next.to, distance[next.to]));
}
}
}
}
static class Node implements Comparable<Node> {
int to;
int cost;
public Node(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
static Input input = new Input();
static class Input {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
public int integer() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return Integer.parseInt(st.nextToken());
}
public String next() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public char[] nToCharArray() throws Exception {
if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
return st.nextToken().toCharArray();
}
}
}
'๐ PS > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
boj-2252 (0) | 2022.08.22 |
---|---|
boj-1850 (0) | 2022.07.23 |
boj-1922 ๋คํธ์ํฌ ์ฐ๊ฒฐ (0) | 2022.07.19 |
boj-1744 ์ ๋ฌถ๊ธฐ (0) | 2022.07.15 |
boj-1300 K๋ฒ์งธ ์ (0) | 2022.07.14 |
๋๊ธ