[伯俊]14938:西江球場(JAVA/ジャワ)
18330 ワード
質問する
BOJ 14938:西江球場-https://www.acmicpc.net/problem/14938
に答える
各地域から全地域への最小経路を求めればよい.すなわち,すべての頂点からすべての頂点への最小経路を求める必要がある.
2つの方法があります.
Dijkstra 알고리즘
を使用する方法および플로이드워셜(Floyd-Warshall) 알고리즘
を使用する方法.Dijkstra
を使用した場合:各領域(着陸領域)においてDijkstraアルゴリズムを回転させ、全領域までの最小距離を求めた後、探索範囲内で可能な物品数を算出し、最大値を印刷する.플로이드워셜
:隣接マトリクスを作成する場合、floywalshアルゴリズムを回転すると、すべてのノードからすべてのノードまでの最短距離が得られます.これにより、各始点の探索範囲内で可能なアイテム数を算出し、最大値を印刷することもできる.コード#コード#
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static final int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
int r = Integer.parseInt(inputs[2]);
int[][] map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i==j) continue;
map[i][j] = INF;
}
}
int[] item_num = new int[n + 1];
inputs = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
item_num[i + 1] = Integer.parseInt(inputs[i]);
}
for (int i = 0; i < r; i++) {
inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
int w = Integer.parseInt(inputs[2]);
map[a][b] = w; // 양방향
map[b][a] = w;
}
// Floyd-Warshall Algorithm
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
// print result
int result = 0;
int cnt = 0;
for (int i = 1; i <= n; i++) {
cnt=0;
for (int j = 1; j <= n; j++) {
if(map[i][j]<=m){
cnt += item_num[j];
}
}
result = Math.max(result, cnt);
}
System.out.println(result);
}
}
整理する
✔ 알고리즘 분류 - 그래프 이론, 다익스트라, 플로이드–와샬
✔ 난이도 - 🟡 Gold 4
🤦♀️ 今日のメッセージ
コメントサイト
いいえ
Reference
この問題について([伯俊]14938:西江球場(JAVA/ジャワ)), 我々は、より多くの情報をここで見つけました https://velog.io/@yanghl98/백준-14938-서강그라운드-JAVA자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol