[백준] 11404 플로이드

백준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;
}