백준 16958번
https://www.acmicpc.net/problem/16958

문제

---

생각하기

---

• 최단 거리 구하기 문제입니다.

• 플로이드 워셜을 사용하여 풀었습니다.

동작

각 노드별 최단 시간을 구한 후 특별한 도시의 경우 이동시간과 텔레포트 시간을 비교하여 최단시간으로 갱신해서 답을 구하면 된다.

전체 노드의 최단 시간을 구해야한다. -> 플로이드 워셜

플로이드 워셜보다 훨씬 더 짧은 시간

결과

코드

---

Floyd

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, T, M;
    private static City[] cities;
    private static int[][] times;
    private static final int INF = Integer.MAX_VALUE / 2;

    private static class City {
        int s;
        int x;
        int y;

        private City(int s, int x, int y) {
            this.s = s;
            this.x = x;
            this.y = y;
        }
    } // End of City class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        // 각 노드별 최단 시간 계산

        floyd();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(times[a][b]).append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static void floyd() {

        // 초기 거리 계산
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    times[i][j] = calc(cities[i].x, cities[i].y, cities[j].x, cities[j].y);
                    if (cities[i].s == 1 && cities[j].s == 1) {
                        times[i][j] = Math.min(times[i][j], T);
                    }
                } else {
                    times[i][j] = 0;
                }
            }
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (times[i][j] > times[i][k] + times[k][j]) {
                        times[i][j] = times[i][k] + times[k][j];
                    }
                }
            }
        }
    } // End of floyd()

    private static int calc(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    } // End of calc()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        cities = new City[N + 1];
        times = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            cities[i] = new City(s, x, y);
            Arrays.fill(times[i], INF);
        }

        M = Integer.parseInt(br.readLine());
    } // End of input()
} // End of Main class

브루트포스(?)

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, T, M;
    private static City[] cities;
    private static int[] times;
    private static List<Integer> specialList;
    private static final int INF = Integer.MAX_VALUE / 2;

    private static class City {
        int s;
        int x;
        int y;

        private City(int s, int x, int y) {
            this.s = s;
            this.x = x;
            this.y = y;
        }
    } // End of City class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= N; i++) {
            if (cities[i].s == 1) continue;
            for (int s : specialList) {
                int dist = calc(cities[i].x, cities[i].y, cities[s].x, cities[s].y);
                times[i] = Math.min(times[i], dist);
            }
        }


        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            int dist = calc(cities[a].x, cities[a].y, cities[b].x, cities[b].y);
            int total = times[a] + times[b] + T;

            sb.append(Math.min(dist, total)).append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static int calc(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    } // End of calc()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        cities = new City[N + 1];
        times = new int[N + 1];
        specialList = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            cities[i] = new City(s, x, y);
            times[i] = INF;

            if (s == 1) {
                times[i] = 0;
                specialList.add(i);
            }
        }

        M = Integer.parseInt(br.readLine());
    } // End of input()
} // End of Main class