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 |