[백준14938] - 서강그라운드

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

14938번: 서강그라운드

---

[문제풀이 전]

다익스트라 알고리즘을 알아야 이 문제를 해결할 수 있습니다. 해당 알고리즘 개념을 모르면 쉬운 개념의 문제부터 익히고 오거나, 검색하셔서 해당 개념을 익히면 금방 풀 수 있는 정도의 난이도입니다.

 

---

[문제풀이]

 

다익스트라를 활용한 문제로 수색할 수 있는 거리가 한정되어 있어, 한 정점에서 다른 정점으로 이동하는 최소거리를 전부 구하여 dist배열에 담아주고,  움직일 수 있는 범위이면 해당 아이템을 얻는 식으로 구현하면 됩니다. 그리고 어느 지점에 떨어지는지는 나오지 않아 모든 정점에서 다익스트라를 시작하여 가장 아이템을 많이 획득할 수 있도록 max값을 가져서 출력하도록 구현하면 문제를 해결할 수 있습니다.

---

[소스코드] 

 

import java.io.*;
import java.util.*;

public class Main {

    static class Node{
        int v;
        int cost;

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    static int n, m, r;
    static ArrayList<Node>[] list;
    static int[] dist, item;
    static boolean[] visit;

    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());
        r = Integer.parseInt(st.nextToken());

        list = new ArrayList[n + 1];
        dist = new int[n + 1];
        visit = new boolean[n + 1];
        item = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            item[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[u].add(new Node(v, w));
            list[v].add(new Node(u, w));
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dijkstra(i));
        }

        System.out.println(ans);
    }

    static int dijkstra(int start) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(visit, false);

        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;

                for (Node next : list[now.v]) {
                    if (!visit[next.v] && dist[next.v] > now.cost + next.cost) {
                        dist[next.v] = now.cost + next.cost;
                        q.add(new Node(next.v, dist[next.v]));
                    }
                }
            }
        }
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            if (m >= dist[i]) {
                sum += item[i];
            }
        }

        return sum;
    }
}