結果
問題 | 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();}}