#807901 (Java21) No.1 道のショートカット

• 問題: No.1 道のショートカット
• ユーザー: ゆうき
• 提出日時: 2022-10-15 18:05:24
• 言語: Java21 (openjdk 21)
• 結果: TLE
• 実行時間: -
• コード長: 6,205 bytes
• コンパイル時間: 4,925 ms
• コンパイル使用メモリ: 94,180 KB
• 実行使用メモリ: 61,200 KB
• 最終ジャッジ日時: 2024-06-26 20:10:13
• 合計ジャッジ時間: 13,167 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	108 ms; 52,932 KB
testcase_01	AC	104 ms; 52,572 KB
testcase_02	AC	106 ms; 52,288 KB
testcase_03	AC	110 ms; 52,540 KB
testcase_04	AC	107 ms; 54,556 KB
testcase_05	AC	110 ms; 52,788 KB
testcase_06	AC	104 ms; 52,560 KB
testcase_07	AC	110 ms; 52,632 KB
testcase_08	AC	120 ms; 52,832 KB
testcase_09	AC	115 ms; 52,728 KB
testcase_10	AC	133 ms; 54,352 KB
testcase_11	TLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.lang.management.ManagementFactory;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.function.IntFunction;

class Main{
  boolean isDebug = ManagementFactory.getRuntimeMXBean().getInputArguments().toString()
      .contains("-agentlib:jdwp");
  final MyReader in = new MyReader(System.in);
  final MyWriter out = new MyWriter(System.out);

  public static void main(final String[] args){ new Main().exe(); }

  private void exe(){
    input();
    preCalc();
    solve();
    out.flush();
  }

  int N = in.it();
  int C = in.it();
  int V = in.it();
  int[] S = in.idx(V);
  int[] T = in.idx(V);
  int[] Y = in.it(V);
  int[] M = in.it(V);

  private void input(){}

  List<List<Edge>> g;
  List<List<Edge>> b;

  int[] bound = new int[N];

  private void preCalc(){
    g = new ArrayList<>();

    for (int i = 0;i < N;i++)
      g.add(new LinkedList<>());

    for (int i = 0;i < V;i++)
      g.get(S[i]).add(new Edge(S[i],T[i],Y[i],M[i]));
    b = new ArrayList<>();

    for (int i = 0;i < N;i++)
      b.add(new LinkedList<>());

    for (int i = 0;i < V;i++)
      b.get(T[i]).add(new Edge(T[i],S[i],Y[i],M[i]));

  }

  void solve(){
    Arrays.fill(bound,Integer.MAX_VALUE);
    bound[N -1] = 0;

    Queue<Integer> que = new PriorityQueue<>(Comparator.comparing(t -> bound[t]));

    que.add(N -1);

    while (!que.isEmpty()) {
      var cur = que.poll();
      for (var e:b.get(cur))
        if (bound[e.t] > bound[e.f] +e.y) {
          bound[e.t] = bound[e.f] +e.y;
          que.add(e.t);
        }
    }

    long ans = dfs(0,0);

    if (ans == Integer.MAX_VALUE)
      out.println(-1);
    else
      out.println(ans);
  }

  private long dfs(final int p,final int y){

    if (C < y +bound[p])
      return Integer.MAX_VALUE;

    if (p == N -1)
      return 0;

    long ret = Integer.MAX_VALUE;
    for (var e:g.get(p))
      ret = Math.min(ret,dfs(e.t,y +e.y) +e.m);

    return ret;
  }

  static class Edge{
    int f;
    int t;
    int y;
    int m;

    public Edge(final int f,final int t,final int y,final int m){
      this.f = f;
      this.t = t;
      this.y = y;
      this.m = m;
    }

  }

  /* 定数 */
  final int mod = (int) 1e9 +7;
  final String yes = "Yes";
  final String no = "No";

  /* 入力 */
  static class MyReader{
    byte[] buf = new byte[1 <<16];
    int head = 0;
    int tail = 0;
    InputStream in;

    public MyReader(final InputStream in){ this.in = in; }

    byte read(){
      if (head == tail) {
        try {
          tail = in.read(buf);
        } catch (IOException e) {
          e.printStackTrace();
        }
        head = 0;
      }
      return buf[head++];
    }

    boolean isPrintable(final byte c){ return 32 < c && c < 127; }

    boolean isNum(final byte c){ return 47 < c && c < 58; }

    byte nextPrintable(){
      byte ret = read();
      return isPrintable(ret) ? ret : nextPrintable();
    }

    int it(){ return (int) lg(); }

    int[] it(final int N){
      int[] a = new int[N];
      Arrays.setAll(a,i -> it());
      return a;
    }

    int[][] it(final int H,final int W){ return arr(new int[H][],i -> it(W)); }

    int idx(){ return it() -1; }

    int[] idx(final int N){
      int[] a = new int[N];
      Arrays.setAll(a,i -> idx());
      return a;
    }

    int[][] idx(final int H,final int W){ return arr(new int[H][],i -> idx(W)); }

    long lg(){
      byte i = nextPrintable();
      boolean negative = i == 45;
      long n = negative ? 0 : i -'0';
      while (isPrintable(i = read()))
        n = 10 *n +i -'0';
      return negative ? -n : n;
    }

    long[] lg(final int N){
      long[] a = new long[N];
      Arrays.setAll(a,i -> lg());
      return a;
    }

    long[][] lg(final int H,final int W){ return arr(new long[H][],i -> lg(W)); }

    char[] ch(){ return str().toCharArray(); }

    char[][] ch(final int H){ return arr(new char[H][],i -> ch()); }

    String line(){
      StringBuilder sb = new StringBuilder();

      byte c;
      while (isPrintable(c = read()) || c == ' ')
        sb.append((char) c);
      return sb.toString();
    }

    String str(){
      StringBuilder sb = new StringBuilder();
      sb.append((char) nextPrintable());
      byte c;
      while (isPrintable(c = read()))
        sb.append((char) c);
      return sb.toString();
    }

    String[] str(final int N){ return arr(new String[N],i -> str()); }

    <T> T[] arr(final T[] arr,final IntFunction<T> f){
      Arrays.setAll(arr,f);
      return arr;
    }
  }

  /* 出力 */
  static class MyWriter{
    OutputStream out;

    byte[] buf = new byte[1 <<16];
    byte[] ibuf = new byte[20];

    int tail = 0;

    public MyWriter(final OutputStream out){ this.out = out; }

    void flush(){
      try {
        out.write(buf,0,tail);
        tail = 0;
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

    void write(final byte b){
      buf[tail++] = b;
      if (tail == buf.length)
        flush();
    }

    void write(final byte[] b,final int off,final int len){
      for (int i = off;i < off +len;i++)
        write(b[i]);
    }

    void write(final char c){ write((byte) c); }

    void write(long n){
      if (n < 0) {
        n = -n;
        write('-');
      }

      int i = ibuf.length;
      do {
        ibuf[--i] = (byte) (n %10 +'0');
        n /= 10;
      } while (n > 0);

      write(ibuf,i,ibuf.length -i);
    }

    void println(final long n){
      write(n);
      write('\n');
    }

    public void println(final double d){ println(String.valueOf(d)); }

    void println(final String s){
      byte[] b = s.getBytes();
      for (byte bb:b)
        write(bb);
      write('\n');
    }

    public void println(final char[] s){
      for (char bb:s)
        write(bb);
      write('\n');
    }

    void println(final int[] a){
      for (int i = 0;i < a.length;i++) {
        if (0 < i)
          write(' ');
        write(a[i]);
      }
      write('\n');
    }

  }
}