๋ฐฉํฅ๊ทธ๋ํ๊ฐ ์ฃผ์ด์ง๋ฉด ์ฃผ์ด์ง ์์์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ์ผ๋ก์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋จ, ๋ชจ๋ ๊ฐ์ ์ ๊ฐ์ค์น๋ 10 ์ดํ์ ์์ฐ์์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ ์ ๊ฐ์ V์ ๊ฐ์ ์ ๊ฐ์ E๊ฐ ์ฃผ์ด์ง๋ค. (1โคVโค20,000, 1โคEโค300,000) ๋ชจ๋ ์ ์ ์๋ 1๋ถํฐ V๊น์ง ๋ฒํธ๊ฐ ๋งค๊ฒจ์ ธ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ๋์งธ ์ค์๋ ์์ ์ ์ ์ ๋ฒํธ K(1โคKโคV)๊ฐ ์ฃผ์ด์ง๋ค. ์ ์งธ ์ค๋ถํฐ E๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ๊ฐ์ ์ ๋ํ๋ด๋ ์ธ ๊ฐ์ ์ ์ (u, v, w)๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์ด๋ u์์ v๋ก ๊ฐ๋ ๊ฐ์ค์น w์ธ ๊ฐ์ ์ด ์กด์ฌํ๋ค๋ ๋ป์ด๋ค. u์ v๋ ์๋ก ๋ค๋ฅด๋ฉฐ w๋ 10 ์ดํ์ ์์ฐ์์ด๋ค. ์๋ก ๋ค๋ฅธ ๋ ์ ์ ์ฌ์ด์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ ์ด ์กด์ฌํ ์๋ ์์์ ์ ์ํ๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค๋ถํฐ V๊ฐ์ ์ค์ ๊ฑธ์ณ, i๋ฒ์งธ ์ค์ i๋ฒ ์ ์ ์ผ๋ก์ ์ต๋จ ๊ฒฝ๋ก์ ๊ฒฝ๋ก๊ฐ์ ์ถ๋ ฅํ๋ค. ์์์ ์์ ์ 0์ผ๋ก ์ถ๋ ฅํ๊ณ , ๊ฒฝ๋ก๊ฐ ์กด์ฌํ์ง ์๋ ๊ฒฝ์ฐ์๋ INF๋ฅผ ์ถ๋ ฅํ๋ฉด ๋๋ค.
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ
โ ์ธ์ ํ๋ ฌ๋ก ๊ตฌํ ์ ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ
๐ก ์ฐ๊ฒฐ๋ ์ ๋ค์ ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํํจ
๐ก ํ์ฌ ์ ์์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์ ๊ตฌํ๋ ๊ฒ์ ์ฐ์ ์์ ํ ์ฌ์ฉ
๐ก ๊ธฐ์กด์ ์๋ ๋น์ฉ๊ณผ ์ ์ ๊ฒฝ์ ํด์ ๊ฐ๋ ๋น์ฉ์ ๋น๊ตํ์ฌ ๋ ์์ ๊ฒ์ ๊ณ ๋ฆ
1) ์ฐ๊ฒฐ๋ ์ ๋ค์ ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํํจ
List<Node>[] edge = new ArrayList[v+1];
for(int i=1; i<v+1; i++)
edge[i] = new ArrayList<>();
for(int i=0; i<e; i++) {
s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
edge[start].add(new Node(end,cost));
}
2) ํ์ฌ ์ ์์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ ์ ๊ตฌํ๋ ๊ฒ์ ์ฐ์ ์์ ํ ์ฌ์ฉ
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(k, 0));
...
while(!pq.isEmpty()){
...
}
3) ๊ธฐ์กด์ ์๋ ๋น์ฉ๊ณผ ์ ์ ๊ฒฝ์ ํด์ ๊ฐ๋ ๋น์ฉ์ ๋น๊ตํ์ฌ ๋ ์์ ๊ฒ์ ๊ณ ๋ฆ
for(Node node : edge[cur]) {
int next = node.end;
int cost = node.cost;
if(dist[next] > dist[cur]+cost) {
dist[next] = dist[cur]+cost;
pq.add(new Node(next, dist[next]));
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Graph_3 {
static int INF = 10000000;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int v = Integer.parseInt(s[0]);
int e = Integer.parseInt(s[1]);
int k = Integer.parseInt(br.readLine());
List<Node>[] edge = new ArrayList[v+1];
int[] dist = new int[v+1];
Arrays.fill(dist, INF);
for(int i=1; i<v+1; i++)
edge[i] = new ArrayList<>();
for(int i=0; i<e; i++) {
s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
edge[start].add(new Node(end,cost));
}
PriorityQueue<Node> pq = new PriorityQueue<>();
boolean[] visited = new boolean[v+1];
pq.add(new Node(k, 0));
dist[k] = 0;
while(!pq.isEmpty()) {
Node curNode = pq.poll();
int cur = curNode.end;
if(visited[cur])
continue;
visited[cur] = true;
for(Node node : edge[cur]) {
int next = node.end;
int cost = node.cost;
if(dist[next] > dist[cur]+cost) {
dist[next] = dist[cur]+cost;
pq.add(new Node(next, dist[next]));
}
}
}
for(int i=1; i<v+1; i++) {
if(dist[i] != INF)
System.out.println(dist[i]);
else
System.out.println("INF");
}
}
static class Node implements Comparable<Node>{
int end, cost;
Node(int end, int cost){
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return cost - o.cost;
}
}
}
์ฑ๊ณตโจ
์ธ์ ํ๋ ฌ๋ก ๊ตฌํํ๋ค๊ฐ ์ธ์ ๋ฆฌ์คํธ, ์ฐ์ ์์ ํ๋ก ๋ฐ๊พธ๋ ๊ณผ์ ์์ ๋ง์ด ํ๋ค์๋ค๐ฑ