[백준 1956] 운동 (C++/Java)

플로이드 와샬 알고리즘으로 푸는 문제이다.

다만 사이클을 어떻게 체크하느냐가 중요할텐데 간단하게 생각해서

arr[i][i]가 INF가 아닌 양수이면 i -> k .. -> i인 루트가 있다는 뜻이므로 arr[i][i]를 비교해주면 된다.

 

#include<cstdio>
#define INF 1000000000
int arr[402][402];
int v,e,from,to,weight,temp=INF;
int main(void){
    scanf("%d %d", &v, &e);
    
    // 초기화
    for(int i=1; i<=v; i++)
        for(int j=1; j<=v; j++)
            arr[i][j]=INF;
    
    // 입력받기 -> 일반통행
    for(int i=0; i<e; i++){
        scanf("%d %d %d", &from, &to, &weight);
        
        arr[from][to]=weight;
    }
    
    // 플로이드 와샬 알고리즘 (사이클까지 계산함)
    for(int k=1; k<=v; k++){
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++){
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
            }
        }
    }
    
    // 사이클 최소값 
    for(int i=1; i<=v; i++){
        if(arr[i][i]<temp){
            temp=arr[i][i];
        }
    }
    
    if(temp==INF) printf("-1");
    else printf("%d", temp);
    
    return 0;
}

 

 

- Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    static int INF = 987654321;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine(), " ");
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int[][] arr = new int[v+1][v+1];
 
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++)
                arr[i][j] = INF;
        }
 
        int from=0, to=0, cost=0;
        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine(), " ");
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            cost = Integer.parseInt(st.nextToken());
 
            arr[from][to] = cost;
        }
 
        for(int k=1; k<=v; k++){
            for(int i=1; i<=v; i++){
                for(int j=1; j<=v; j++){
                    arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
                }
            }
        }
 
        int ans = INF;
        for(int i=1; i<=v; i++){
            if(ans > arr[i][i])
                ans = arr[i][i];
        }
 
        if(ans == INF) System.out.println("-1");
        else System.out.println(ans);
    }
}