n(2 โค n โค 100)๊ฐ์ ๋์๊ฐ ์๋ค. ๊ทธ๋ฆฌ๊ณ ํ ๋์์์ ์ถ๋ฐํ์ฌ ๋ค๋ฅธ ๋์์ ๋์ฐฉํ๋ m(1 โค m โค 100,000)๊ฐ์ ๋ฒ์ค๊ฐ ์๋ค. ๊ฐ ๋ฒ์ค๋ ํ ๋ฒ ์ฌ์ฉํ ๋ ํ์ํ ๋น์ฉ์ด ์๋ค.
๋ชจ๋ ๋์์ ์ (A, B)์ ๋ํด์ ๋์ A์์ B๋ก ๊ฐ๋๋ฐ ํ์ํ ๋น์ฉ์ ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋์์ ๊ฐ์ n์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ ๋ฒ์ค์ ๊ฐ์ m์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ ์งธ ์ค๋ถํฐ m+2์ค๊น์ง ๋ค์๊ณผ ๊ฐ์ ๋ฒ์ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒ์์๋ ๊ทธ ๋ฒ์ค์ ์ถ๋ฐ ๋์์ ๋ฒํธ๊ฐ ์ฃผ์ด์ง๋ค. ๋ฒ์ค์ ์ ๋ณด๋ ๋ฒ์ค์ ์์ ๋์ a, ๋์ฐฉ ๋์ b, ํ ๋ฒ ํ๋๋ฐ ํ์ํ ๋น์ฉ c๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ์์ ๋์์ ๋์ฐฉ ๋์๊ฐ ๊ฐ์ ๊ฒฝ์ฐ๋ ์๋ค. ๋น์ฉ์ 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์์ ๋์์ ๋์ฐฉ ๋์๋ฅผ ์ฐ๊ฒฐํ๋ ๋ ธ์ ์ ํ๋๊ฐ ์๋ ์ ์๋ค.
์ถ๋ ฅ
n๊ฐ์ ์ค์ ์ถ๋ ฅํด์ผ ํ๋ค. i๋ฒ์งธ ์ค์ ์ถ๋ ฅํ๋ j๋ฒ์งธ ์ซ์๋ ๋์ i์์ j๋ก ๊ฐ๋๋ฐ ํ์ํ ์ต์ ๋น์ฉ์ด๋ค. ๋ง์ฝ, i์์ j๋ก ๊ฐ ์ ์๋ ๊ฒฝ์ฐ์๋ ๊ทธ ์๋ฆฌ์ 0์ ์ถ๋ ฅํ๋ค.
๐ก ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ
โ ๋ชจ๋ ์ ์ ์ฌ์ด์ ์ต๋จ๊ฑฐ๋ฆฌ ์ฐพ๊ธฐ (n:m)
VS ๋ค์ต์คํธ๋ผ๋ ํ ์ ์ ์์ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ ์ฐพ๊ธฐ (1:n)
๐ก ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์ ์ ๋น์ฉ์ผ๋ก ๋ฐฐ์ด์ ์ฝ์
๐ก ํ ์ ์ ๊ฒฝ์ ํด์ ๊ฐ๋ ๋น์ฉ์ ๊ตฌํ ํ, ์ด์ ๋น์ฉ๊ณผ ๋น๊ตํ์ฌ ๋ ์์ ์๋ก ๊ฐฑ์ ํจ
1) ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์ ์ ๋น์ฉ์ผ๋ก ๋ฐฐ์ด์ ์ฝ์
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(i == j)
continue;
arr[i][j] = INF;
}
}
2) ํ ์ ์ ๊ฒฝ์ ํด์ ๊ฐ๋ ๋น์ฉ์ ๊ตฌํ ํ, ์ด์ ๋น์ฉ๊ณผ ๋น๊ตํ์ฌ ๋ ์์ ์๋ก ๊ฐฑ์ ํจ
for(int mid=1; mid<n+1; mid++) {
for(int start=1; start<n+1; start++) {
for(int end=1; end<n+1; end++) {
arr[start][end] = Math.min(arr[start][mid]+arr[mid][end], arr[start][end]);
}
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Graph_2 {
static int[][] arr;
static int INF = 10000000;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
arr = new int[n+1][n+1];
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(i == j)
continue;
arr[i][j] = INF;
}
}
for(int i=0; i<m; i++) {
String[] s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);
int end = Integer.parseInt(s[1]);
int cost = Integer.parseInt(s[2]);
arr[start][end] = Math.min(cost,arr[start][end]);
}
for(int mid=1; mid<n+1; mid++) {
for(int start=1; start<n+1; start++) {
for(int end=1; end<n+1; end++) {
arr[start][end] = Math.min(arr[start][mid]+arr[mid][end], arr[start][end]);
}
}
}
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(arr[i][j] >= INF)
sb.append("0 ");
else
sb.append(arr[i][j]+" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
}
์ฑ๊ณตโจ
(INF ๊ฐ์ Integer.MAX_VALUE๋ก ์ก์๋ค๊ฐ ๊ณ์ ํ๋ ธ๋ค. Integer.MAX_VALUE์์ ๋ค๋ฅธ ์ซ์๋ค์ ๋ํ ๋๋ฅผ ๊ณ ๋ คํ์ง ์์๋ค๐ฑ)