백준 [자바 java] 1956번 : 운동

문제설명

v개의 마을이 있고, 각 마을로 가는 비용이 주어질 때 특정 마을을 왔다갔다 하는 비용 중 가장 작은 비용을 구하는 문제이다.

 

풀이

전형적인 다익스트라 문제이다.

하나의 노드에 대한 다익스트라만 구하는 것이 아닌, 모든 노드에 대해서 구해야하므로 2차원배열을 사용하였다.

 

for(int i = 1;i<=v;i++){
      for(int j = 1;j<=v;j++){
        if(dix[i][j] != Integer.MAX_VALUE && dix[j][i] != Integer.MAX_VALUE){
          if(dix[i][j] + dix[j][i] < ans){
            ans = dix[i][j] + dix[j][i];
          }
        }
      }
    }

다익스트라 배열을 다 채운 후, 해당 값이 아직 Integer.MAX_VALUE인 경우 해당 노드는 거치치 않은 것으로 판단할 수 있기 때문에 배열 계산에서 제외했다.(MAX_VALUE와 MAX_VALUE를 더하면 오버플로우 발생할 수 있기 때문)

 

 if(ans == Integer.MAX_VALUE){
      System.out.println(-1);
    }
    else System.out.println(ans);

만약 위 과정을 다 겨쳤는데도 ans가 max_value인 경우에는 왕복이 불가능하다는 이야기이므로

-1을 출력하도록 한다.

 

-1 출력하는거 까먹어서 한번 틀렸다..

 

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