[SWEA] [Professional] 운동

Posted on | In |

문제 보러가기

제한사항

각 테스트 케이스의 두 번째 줄부터 M개의 줄에 걸쳐 도로의 정보 s, e, c가 주어진다.

이는 s번 건물으로부터 e번 건물으로 이동하는 길이 c의 일방 통행 도로가 있다는 의미이다.

거리는 10,000 이하의 자연수이고, 같은 시작점과 도착점을 가진 간선은 최대 한 개 등장한다.

각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 도로의 길이의 합이 가장 작은 사이클의 길이를 출력한다. 만약, 그러한 사이클을 찾을 수 없다면 -1을 출력한다.

첫번째 생각

과거에 만들어놨던 Input을 사용해보았다. bufferedReader가 Scanner에 비해 속도는 빠르지만 사용법이 불편함 점 단점을 해결하는 Input 방법이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    static class In {
        static BufferedReader br;
        static StringTokenizer token;

        static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            token = new StringTokenizer("");
        }

        static String readLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        static String next() {
            while (!token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(br.readLine());
                } catch (IOException e) {

                }
            }
            return token.nextToken();
        }
        
        static int nextInt() {
            return Integer.parseInt(next());
        }
    }

bfs 탐색을 통해 최솟값을 이루는 사이클을 찾는다.

index는 방문한 건물의 수를 나타내며 dis 배열은 거리의 합을 나타낸다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        In.init();
        int T = In.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int N = In.nextInt();
            int M = In.nextInt();
            int[][] costs = new int[N + 1][N + 1];
            for (int i = 0; i < M; i++) {
                int s = In.nextInt();
                int e = In.nextInt();
                costs[s][e] = In.nextInt();
            }
            int result = Integer.MAX_VALUE;
            int index = 1;
            while (index < N + 1) {
                PriorityQueue<Cost> queue = new PriorityQueue<>();
                int[] dis = new int[N + 1];
                Arrays.fill(dis, Integer.MAX_VALUE);
                for (int i = 1; i < N + 1; i++) {
                    if (costs[index][i] > 0) {
                        queue.add(new Cost(i, costs[index][i]));
                        dis[i] = costs[index][i];
                    }
                }
                while (!queue.isEmpty()) {
                    Cost cost = queue.poll();
                    if (cost.s == index)
                        break;
                    if (cost.cost > dis[cost.s])
                        continue;
                    for (int i = 1; i < N + 1; i++) {
                        if (costs[cost.s][i] > 0 && dis[i] > costs[cost.s][i] + dis[cost.s]) {
                            dis[i] = costs[cost.s][i] + dis[cost.s];
                            queue.add(new Cost(i, dis[i]));
                        }
                    }
                }
                result = result < dis[index] ? result : dis[index];
                index++;
            }
            if (result != Integer.MAX_VALUE)
                System.out.println("#" + tc + " " + result);
            else
                System.out.println("#" + tc + " -1");
        }
    }
    static class Cost implements Comparable<Cost> {
        int s, cost;

        Cost(int s, int cost) {
            this.s = s;
            this.cost = cost;
        }

        @Override
        public int compareTo(Cost o) {
            if (this.cost < o.cost)
                return -1;
            else if (this.cost > o.cost)
                return 1;
            return 0;
        }
    }
    static class In {
        static BufferedReader br;
        static StringTokenizer token;

        static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            token = new StringTokenizer("");
        }

        static String readLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        static String next() {
            while (!token.hasMoreTokens()) {
                try {
                    token = new StringTokenizer(br.readLine());
                } catch (IOException e) {

                }
            }
            return token.nextToken();
        }
        
        static int nextInt() {
            return Integer.parseInt(next());
        }
    }
}