11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
[난이도] Gold4
[유형] 플로이드 워셜
[풀이] 플로이드 워셜
#include <cstdio>
#include <algorithm>
int N,M,dist[101][101],INF=9e8;
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) {
for(int j=1;j<=N;j++) {
dist[i][j] = INF;
if(i==j) dist[i][j] = 0;
}
}
for(int i=0;i<M;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c < dist[a][b]) dist[a][b] = c;
}
for(int k=1;k<=N;k++){
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
dist[i][j] = std::min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
printf("%d ",dist[i][j]==INF ? 0:dist[i][j]);
}
puts("");
}
}
github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/11404.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 1199 : 오일러 회로(C++) (0) | 2020.12.12 |
|---|---|
| [BOJ/백준][Gold4] 11657 : 타임머신(C++) (0) | 2020.12.12 |
| [BOJ/백준][Gold4] 10830 : 행렬 제곱(C++) (0) | 2020.12.12 |
| [BOJ/백준][Gold4] 1403 : 거짓말(C++) (0) | 2020.12.12 |
| [BOJ/백준][Gold4] 1022 : 소용돌이 예쁘게 출력하기 (C++) (0) | 2020.12.12 |