[백준] 11404 플로이드
입력
n(2 ≤ n ≤ 100)개의 도시
m(1 ≤ m ≤ 100,000)개의 버스
출발도시 / 도착도시 / 비용(1 ≤ m ≤ 100,000)
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
출력
n개의 줄을 출력
i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용
만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력
풀이
플로이드-와샬(Floyd Warshall)
- 모든 정점에서 모든 정점으로의 최단경로
- 3중 for문을 통해 거쳐가는 정점에 대한 비용 계산하여 비교
distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
처음에 문제를 잘 안읽고 플로이드 코드만 짰을 때는 계속 잘못된 값이 나왔다
-> 입력 조건에서 노선이 하나가 아닐 수 있다고 했기 때문에 여러 노선의 경우 최소값을 넣어야 한다.
#include <iostream>
#include <algorithm>
#define INF 1e9
#define MAXN 101
using namespace std;
long long cost[MAXN][MAXN];
int main() {
int N,M;
cin>>N;
cin>>M;
for(int i=0;i<=N;i++){
fill(cost[i],cost[i]+MAXN,INF); //무한대로 초기화
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i==j){
cost[i][j]=0; //자기 자신은 0으로
}
}
}
for(int i=0;i < M;i++){
int a,b,c;
cin>>a>>b>>c;
//입력되는 경로가 중복되는 경우 최소값으로
if(cost[a][b]>c){
cost[a][b] = c;
}
}
for(int k=1;k<=N;k++){ //경유지
for(int a=1;a<=N;a++){ //출발점
for(int b=1;b<=N;b++){ //도착점
cost[a][b]=min(cost[a][b],cost[a][k]+cost[k][b]);
}
}
}
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(cost[i][j]==INF){ //갈 수 없는 경우
cout<<0<<" ";
}else{
cout<<cost[i][j]<<" ";
}
}
cout<<"\n";
}
return 0;
}
Author And Source
이 문제에 관하여([백준] 11404 플로이드), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@botong_99/백준-11404-플로이드저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)