結果
問題 |
No.1382 Travel in Mitaru city
|
ユーザー |
![]() |
提出日時 | 2021-02-08 11:26:46 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 878 ms / 2,000 ms |
コード長 | 1,997 bytes |
コンパイル時間 | 2,125 ms |
コンパイル使用メモリ | 78,756 KB |
実行使用メモリ | 72,152 KB |
最終ジャッジ日時 | 2024-07-05 07:47:49 |
合計ジャッジ時間 | 34,981 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
ソースコード
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" ", 4); int n = Integer.parseInt(first[0]); int m = Integer.parseInt(first[1]); int s = Integer.parseInt(first[2]) - 1; int t = Integer.parseInt(first[3]) - 1; String[] second = br.readLine().split(" ", n); Town[] towns = new Town[n]; ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { towns[i] = new Town(i, Integer.parseInt(second[i])); graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { String[] line = br.readLine().split(" ", 2); int a = Integer.parseInt(line[0]) - 1; int b = Integer.parseInt(line[1]) - 1; graph.get(a).add(b); graph.get(b).add(a); } PriorityQueue<Town> queue = new PriorityQueue<>(); queue.add(towns[s]); boolean[] visited = new boolean[n]; visited[s] = true; int score = Integer.MAX_VALUE; int count = 0; while (queue.size() > 0) { Town y = queue.poll(); if (score > y.value) { score = y.value; count++; } for (int x : graph.get(y.idx)) { if (!visited[x]) { queue.add(towns[x]); visited[x] = true; } } } System.out.println(count - 1); } static class Town implements Comparable<Town> { int idx; int value; public Town(int idx, int value) { this.idx = idx; this.value = value; } public int compareTo(Town another) { return another.value - value; } } }