結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 15:38:24 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 772 ms / 2,000 ms |
コード長 | 1,335 bytes |
コンパイル時間 | 2,667 ms |
コンパイル使用メモリ | 81,928 KB |
実行使用メモリ | 62,880 KB |
最終ジャッジ日時 | 2024-09-26 19:04:33 |
合計ジャッジ時間 | 24,758 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
import java.util.*; import java.io.*; class Main{ private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static final PrintWriter out = new PrintWriter(System.out); public static void main(String[] args)throws IOException{ String[] str = br.readLine().split(" "); int N = Integer.parseInt(str[0]); int M = Integer.parseInt(str[1]); ArrayList<ArrayList<Integer>> list = new ArrayList<>(); for(int i=0;i<=N;i++) list.add(new ArrayList<>()); while(M-->0){ str = br.readLine().split(" "); int u = Integer.parseInt(str[0]); int v = Integer.parseInt(str[1]); list.get(u).add(v); } PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(a[1],b[1])); int[] dist = new int[4*N+1]; Arrays.fill(dist,Integer.MAX_VALUE); dist[1] = 0; queue.add(new int[]{1,0,0}); while(queue.size()>0){ int[] now = queue.poll(); if(dist[now[0]+now[2]*N]<now[1]) continue; for(int next:list.get(now[0])){ int nextP = next==N-1?now[2]|1:next==N?now[2]|2:now[2]; if(dist[now[0]+now[2]*N]+1<dist[next+nextP*N]){ dist[next+nextP*N] = dist[now[0]+now[2]*N]+1; queue.add(new int[]{next,dist[next+nextP*N],nextP}); } } } out.println(dist[3*N+1]==Integer.MAX_VALUE?-1:dist[3*N+1]); br.close(); out.close(); } }