[백준] 14938 서강그라운드 - 다익스트라(Dijkstra) JAVA

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

14938번: 서강그라운드

코드설명

다익스트라 문제입니다.

 

길의 개수 r (1 ≤ r ≤ 100), 길의 길이 l (1 ≤ l ≤ 15) 이기에 최대 INF = 100 * 15 = 1500 입니다.

우선순위큐를 활용한 다익스트라의 시간복잡도는 O(E log V) 입니다.

 

문제로직은,

각 시작점에서의 모든 노드까지의거리를 구한뒤 m 만큼 떨어져있는 곳의 지역의 모든 아이템들의 합을 비교하여 정답을 내면 되는 문제입니다.

 

코드

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int n, m, r, t;
	public static int[] arr;
	public static int answer = 0;
	public static int[] d;
	public static int INF = 15 * 100;
	public static int[] item;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    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());
    	
    	for(int i=0;i<=n;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	item = new int[n+1];
    	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 nodeA = Integer.parseInt(st.nextToken());
    		int nodeB = Integer.parseInt(st.nextToken());
    		int nodeDist = Integer.parseInt(st.nextToken());
    		graph.get(nodeA).add(new Node(nodeB, nodeDist));
    		graph.get(nodeB).add(new Node(nodeA, nodeDist));
    	}
    	
    	for(int i=1;i<=n;i++) {
    		dijkstra(i);
    		int temp = 0;
    		for(int j=1;j<d.length;j++) {
    			if( d[j] <= m) {
    				temp += item[j];
    			}
    		}
    		answer = Math.max(answer,  temp);
    	}
    	System.out.println(answer);
    	
    }
    
    public static void dijkstra(int start) {
    	d = new int[n+1];
    	Arrays.fill(d,  INF);
    	PriorityQueue<Node> pq = new PriorityQueue<Node>();
    	d[start] = 0;
    	pq.offer(new Node(start, 0));
    	
    	while(!pq.isEmpty()) {
    		
    		Node temp = pq.poll();
    		int now = temp.nodeB;
    		int dist = temp.dist;
    		if(d[now] < dist) continue;
    		for(int i=0;i<graph.get(now).size();i++) {
    			int cost = d[now] + graph.get(now).get(i).dist; 
    			if(d[graph.get(now).get(i).nodeB] > cost) {
    				d[graph.get(now).get(i).nodeB] = cost;
    				pq.offer(new Node(graph.get(now).get(i).nodeB, cost));
    			}
    		}
    	}
    }
    
}

class Node implements Comparable<Node>{
	int nodeB;
	int dist;
	public Node(int nodeB, int dist) {
		this.nodeB = nodeB;
		this.dist = dist;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.dist > other.dist) {
			return 1;
		}else if(this.dist == other.dist) {
			return 0;
		} else {
			return -1;
		}
	}
}