서강 그라운드

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

풀이

예은이가 그래프의 한 지점으로 낙하했을 때 얻을 수 있는 아이템의 개수를 구하고 이를 그래프의 모든 지점에 대해 반복하여 최대를 찾으면 된다.

플로이드-와샬 알고리즘을 통해 모든 노드에 대한 경로의 비용을 찾고 거기서 예은이의 수색범위 내의 지점의 아이템의 개수만을 구해도 되지만 음의 간선이 없기때문에 다익스트라 알고리즘을 지점 개수만큼 반복하는 것으로 풀이했다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static ArrayList<Pair>[] graph;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        int range = Integer.parseInt(input[1]);
        m = Integer.parseInt(input[2]);
        int[] items = new int[n + 1];

        String[] second = br.readLine().split(" ");
        for (int i = 1; i <= n; i++)
            items[i] = Integer.parseInt(second[i - 1]);

        graph = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++)
            graph[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            graph[x].add(new Pair(y, w));
            graph[y].add(new Pair(x, w));
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int w = 0;
            int[] dist = dijkstra(i);
            for (int j = 1; j <= n; j++) {
                if (dist[j] <= range) {
                    w = w + items[j];
                }
            }
            max = Math.max(w, max);
        }

        System.out.println(max);
        bw.close();
        br.close();
    }

    private static int[] dijkstra(int start) {
        int[] dist = new int[n + 1];
        int[] route = new int[n + 1];
        boolean[] visit = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i == start) {
                dist[i] = 0;
                route[i] = 1;
            } else
                dist[i] = Integer.MAX_VALUE;
        }
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        queue.offer(new Pair(start, 0));
        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            int y = p.dest;
            if (visit[y])
                continue;
            else
                visit[y] = true;
            for (Pair next : graph[y]) {
                if (dist[next.dest] >= dist[y] + next.weight) {
                    dist[next.dest] = dist[y] + next.weight;
                    //route[next.dest] = y;
                    queue.offer(new Pair(next.dest, dist[next.dest]));
                }
            }
        }
        return dist;
    }

}

class Pair implements Comparable<Pair> {
    public int dest;
    public int weight;

    public Pair(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }

    @Override
    public int compareTo(Pair o) {
        return Integer.compare(this.weight, o.weight);
    }
}