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

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

[문제링크]

0. m 이하의 cost로 방문 가능한 노드가 가장 많은 노드 찾기

다익스트라를 n번 돌리거나, 플로이드-와샬 진행

1. 편의를 위해, 갈 수 없는 노드는 큰 값(2000)으로 초기화한다

최대 거리가 15, 노드가 100개이므로 두 노드의 거리는 15*99=1485가 최대값이다

2. 노드 간 거리 정보를 저장하고, 플로이드-와샬을 진행해 각 노드간 거리를 구한다

3. 각 노드 별 방문 가능한 노드들로부터 획득 아이템 갯수를 종합, 최댓값을 출력한다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = pint(st.nextToken()); int m = pint(st.nextToken()); int r = pint(st.nextToken()); int[][]map=new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(map[i], 2000); } int[] item=new int[n]; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { item[i]=pint(st.nextToken()); } for (int i = 0; i < r; i++) { st = new StringTokenizer(br.readLine()); int n1 = pint(st.nextToken())-1; int n2 = pint(st.nextToken())-1; int c = pint(st.nextToken()); map[n1][n2]=c; map[n2][n1]=c; } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if(i==k)continue; for (int j = 0; j < n; j++) { if(i==j)continue; map[i][j]=Math.min(map[i][j],map[i][k]+map[k][j]); } } } int max_item=0; for (int i = 0; i < n; i++) { map[i][i]=0; int temp=0; for (int j = 0; j < n; j++) { if(map[i][j]<=m) { temp+=item[j]; } } max_item=Math.max(temp, max_item); } System.out.println(max_item); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/134 by ccl(S) rewrite - 2021-10-03 02:01:06