백준 : 1504

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

1504번: 특정한 최단 경로

 

플로이드 와샬 알고리즘

1인 노드에서 특정 a,b를 지나고 N을 간다는 것은

 

1->a->b->N 방법과 1->b->a->N 방법이 있다.

물론 1->a는 항상 최단거리로 가야한다. 이럴땐 플로이드 와샬 알고리즘을 사용한다.

 

digit[][] 배열을 NXN 크기 만큼 공간을 할당한다.

예를들어 가상의 노드

 

Node  ,  Node  :  Weight 이라고 가정할 때

예시는

1 , 2 : 3

1 , 3 : 5

1 , 4 : 4

2 , 3 : 3

2 , 4 : 5

0	3	5	4
3	0	3	5
5	3	0	1
4	5	1	0

값이 세워진다 실제 연결되지 않은 노드는 INF 값으로 초기화 시킨다.

 

이제 1~4 노드를 기준으로 digit값들을 초기화 한다. 

1을 기준으로 할때 2 3 4 노드들중에서 현재 digit값과 1을 경유하고 그 위치로 갓을때 값을 비교하여 최소인 값으로 초기화한다. 이렇게하면 모든 노드에 대해서 도착지의 최소값을 얻을 수가 있다.

 

이렇게 플로이드 와샬을 이용해서 digit[][] 을 채우고 나서

 

1->a->b->N 값과 1->b->a->N 값중 최소인값이 정답이 된다.

주의 할점은 1->a 또는 1->b 가 하나라도 INF값이 된다면 a와,b를 지나가지 못한다는 뜻이다.

 

package com.ssay.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class B1504 {
    static int MAX_VALUE = 987654321;
    public static class Vertex implements Comparable<Vertex> {
        int u;
        int w;
 
        public Vertex(int u, int w) {
            super();
            this.u = u;
            this.w = w;
        }
 
        @Override
        public int compareTo(Vertex o) {
            // TODO Auto-generated method stub
            return Integer.compare(this.w, o.w);
        }
 
    }
 
    static int N;
    static int M;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        int[][] digit = new int[N + 1][N + 1];
 
        for (int n = 1; n <= N; n++) {
            Arrays.fill(digit[n], MAX_VALUE);
            digit[n][n] = 0;
        }
 
        int u, v, w;
 
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            digit[u][v] = w;
            digit[v][u] = w;
 
        }
 
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
 
        // 플로이드 와샬 알고리즘 구현
 
        for (int n = 1; n <= N; n++) {
            for (int i = 1; i <= N; i++) {
                if (i == n) {
                    continue;
                }
                for (int j = 1; j <= N; j++) {
                    // 자기자신 가는 경로는 0
                    if (j == i || j == n)
                        continue;
 
                    digit[i][j] = Math.min(digit[i][j], digit[i][n] + digit[n][j]);
 
                }
            }
        }
        
        if(digit[1][a] == MAX_VALUE || digit[1][b] == MAX_VALUE) {
            System.out.println(-1);
        }else {
            
            int ab = digit[1][a] + digit[a][b] + digit[b][N];
            int ba = digit[1][b] + digit[b][a] + digit[a][N];
            
            int result = Math.min(ab, ba);
            
            System.out.println(result);
        }
 
    }
}