아이디어

• $n \le 100$ 정도이므로 Floyd-Warshall을 떠올려 볼 수 있다.
• Floyd-Warshall을 사용해 그래프의 모든 두 정점간 최단 거리를 구하자.
• 각 $v_1$에 대하여 $v_1 \rightarrow v_2$ 최단 경로가 $m$ 이하인 $v_2$의 합 중 최댓값이 답이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int n, m, r, t[], ans = 0;
    static boolean[] visited;

    static int[][] dist;

    static final int INF = Integer.MAX_VALUE / 2;

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        n = Integer.parseInt(tk.nextToken());
        m = Integer.parseInt(tk.nextToken());
        r = Integer.parseInt(tk.nextToken());

        t = new int[n+1];
        tk = new StringTokenizer(rd.readLine());
        for (int i=1; i<=n; i++)
            t[i] = Integer.parseInt(tk.nextToken());

        dist = new int[n+1][n+1];
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                dist[i][j] = i == j ? 0 : INF;
            }
        }

        for (int i=0; i<r; i++) {
            tk = new StringTokenizer(rd.readLine());
            int a = Integer.parseInt(tk.nextToken());
            int b = Integer.parseInt(tk.nextToken());
            int l = Integer.parseInt(tk.nextToken());
            dist[a][b] = dist[b][a] = Math.min(dist[a][b], l);
        }

        for (int k=1; k<=n; k++) {
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for (int i=1; i<=n; i++) {
            int sum = 0;
            for (int j=1; j<=n; j++) {
                if (dist[i][j] <= m)
                    sum += t[j];
            }
            ans = Math.max(ans, sum);
        }

        System.out.println(ans);
    }
}

메모리 및 시간

• 메모리: 14648 KB
• 시간: 152 ms

리뷰

• SSAFY 프로젝트 끝! 알고리즘 재활 시작!
• 첫 재활운동은 간단한 CLASS 4 문제로 시작했다.