백준 1956번. 운동(c++) / 플로이드 와샬

전형적인 플로이드 와샬 문제이다.

거쳐가는 점, 출발 점, 도착 점을 3중 for문으로 돌아 dp값을 계속 갱신해주었다.

그 후에는 i->i로 의 경로중 가장 최소 값을 구해주었다.

 

 

코드 첨부

// 운동(플로이드 와샬)
#include <iostream>
#include <climits>
using namespace std;
 
int v, e, a, b, c;
int dp[401][401] = {0, };
int road[401][401] = {0, };
int total = INT_MAX;
 
int main()
{
    cin>>v>>e;
    for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            dp[i][j] = INT_MAX;
        }   
    }
    for(int i=0; i<e; i++){
        cin>>a>>b>>c;
        dp[a][b] = min(dp[a][b], c);
    }
 
    // 거쳐가는 점
    for(int i=1; i<=v; i++){
        // 출발 점
        for(int j=1; j<=v; j++){
            // 도착 점
            for(int k=1; k<=v; k++){
                if(dp[j][i]!=INT_MAX && dp[i][k]!=INT_MAX){
                    if(dp[j][i]+dp[i][k]<dp[j][k]){
                        dp[j][k] = dp[j][i]+dp[i][k];
                    }
                }
            }
        }
    }
 
    for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            if(i==j){
                total = min(total, dp[i][j]);
            }
        }
    }
 
    if(total==INT_MAX){
        cout<<"-1"<<"\n";
    }else{
        cout<<total<<"\n";
    }
 
    return 0;
}

 

문제 첨부

https://www.acmicpc.net/problem/1956

1956번: 운동