|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
#define INF 999999999
int arr[102][102];
int n,m,a,b,c,temp;
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
arr[i][j]=(i==j)?0:INF;
}
}
for(int i=0; i<m; i++){
cin >> a >> b >> c;
arr[a][b]=min(arr[a][b],c);
}
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]>arr[i][k]+arr[k][j])
arr[i][j]=arr[i][k]+arr[k][j];
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(arr[i][j]==INF)
cout << "0" << " ";
else
cout << arr[i][j] << " ";
}
cout << "\n";
}
return 0;
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main{
static int maxNum = 1000000000;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력받기
int n = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int m = Integer.parseInt(br.readLine());
// 배열 전처리
for(int i=0; i<n; i++){
for(int j=0; j<n; j++)
arr[i][j] = maxNum;
}
// m개의 버스정보 입력받기
StringTokenizer st; int a=0, b=0, c=0;
for(int i=0; i<m; i++){
st = new StringTokenizer(br.readLine(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
arr[a-1][b-1] = Math.min(arr[a-1][b-1], c);
}
// 플로이드 와샬 알고리즘
for(int k=0; k<n; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
}
}
}
//
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==j) sb.append("0").append(" ");
else if(arr[i][j] == maxNum) sb.append("0").append(" ");
else sb.append(arr[i][j]).append(" ");
} sb.append("\n");
}
System.out.println(sb);
}
}
|
cs |
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 1261] 알고스팟 (C++) (0) | 2020.12.08 |
|---|---|
| [백준 2206] 벽 부수고 이동하기 (C++/Python) (0) | 2020.12.08 |
| [백준 3055] 탈출 (C++) (0) | 2020.12.08 |
| [백준 5427] 불 (C++/Python) (0) | 2020.12.08 |
| [백준 14442] 벽 부수고 이동하기 2 (0) | 2020.12.08 |