結果

問題 No.1 道のショートカット
ユーザー C++ C++
提出日時 2024-06-18 02:09:38
言語 Java21
(openjdk 21)
結果
AC  
実行時間 301 ms / 5,000 ms
コード長 6,738 bytes
コンパイル時間 7,532 ms
コンパイル使用メモリ 85,940 KB
実行使用メモリ 57,444 KB
最終ジャッジ日時 2024-06-18 02:09:53
合計ジャッジ時間 13,039 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
51,044 KB
testcase_01 AC 76 ms
51,060 KB
testcase_02 AC 73 ms
50,808 KB
testcase_03 AC 74 ms
51,012 KB
testcase_04 AC 71 ms
51,084 KB
testcase_05 AC 73 ms
51,120 KB
testcase_06 AC 74 ms
51,076 KB
testcase_07 AC 71 ms
51,072 KB
testcase_08 AC 135 ms
53,320 KB
testcase_09 AC 91 ms
51,824 KB
testcase_10 AC 125 ms
51,896 KB
testcase_11 AC 173 ms
55,580 KB
testcase_12 AC 237 ms
57,364 KB
testcase_13 AC 204 ms
57,052 KB
testcase_14 AC 83 ms
51,056 KB
testcase_15 AC 72 ms
51,128 KB
testcase_16 AC 80 ms
51,224 KB
testcase_17 AC 71 ms
50,840 KB
testcase_18 AC 75 ms
51,168 KB
testcase_19 AC 74 ms
50,820 KB
testcase_20 AC 103 ms
51,824 KB
testcase_21 AC 78 ms
51,252 KB
testcase_22 AC 77 ms
51,348 KB
testcase_23 AC 230 ms
57,164 KB
testcase_24 AC 283 ms
57,444 KB
testcase_25 AC 110 ms
51,848 KB
testcase_26 AC 103 ms
51,876 KB
testcase_27 AC 194 ms
56,880 KB
testcase_28 AC 70 ms
51,104 KB
testcase_29 AC 139 ms
53,472 KB
testcase_30 AC 84 ms
51,760 KB
testcase_31 AC 113 ms
51,944 KB
testcase_32 AC 144 ms
53,144 KB
testcase_33 AC 117 ms
52,008 KB
testcase_34 AC 301 ms
57,212 KB
testcase_35 AC 80 ms
51,348 KB
testcase_36 AC 94 ms
51,848 KB
testcase_37 AC 86 ms
51,944 KB
testcase_38 AC 72 ms
51,088 KB
testcase_39 AC 74 ms
51,088 KB
testcase_40 AC 79 ms
51,212 KB
testcase_41 AC 72 ms
50,988 KB
testcase_42 AC 70 ms
51,048 KB
testcase_43 AC 68 ms
50,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.*;
import java.util.function.IntFunction;
/*
class Pair<F, S> extends java.util.AbstractMap.SimpleImmutableEntry<F, S> {
  public  Pair( F f, S s ) { super( f, s );  }
  public F getFirst() { return getKey(); }
  public S getSecond() { return getValue(); }
  public String toString() { return "["+getKey()+","+getValue()+"]"; }
} 
*/
class Pair<A, B> implements Comparable<Pair<A, B>> {
  public A first;
  public B second;

  public Pair(A firstVal, B secondVal) { //Inspired by Egor Kulikov's GitHub contributions
      this.first = firstVal; //Rewritten and modified by me (Jay Leeds)
      this.second = secondVal;
  }


  public boolean equals(Object o) {
      if (o == null || getClass() != o.getClass()) {
          return false;
      }
      Pair p = (Pair) o;
      return this.compareTo(p) == 0;
  }

  public int compareTo(Pair<A, B> p) {
      if (p.first instanceof Comparable) {
          int firstCompare = ((Comparable<A>) first).compareTo(p.first);
          if (firstCompare != 0) return firstCompare;
      }
      if (p.second instanceof Comparable) {
          return ((Comparable<B>) second).compareTo(p.second);
      }
      return 0;
  }
}

public class Main{
  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();
  }

  private void input(){}

  private void preCalc(){}
  
  static class Route implements Comparable<Route>{
    int idx, cost, time;
    public Route(int idx, int cost, int time){
      this.idx = idx;
      this.cost = cost;
      this.time = time;
    }
    public int compareTo(Route other){
      return time - other.time;
    }
  }

  void solve(){
    int INF = Integer.MAX_VALUE;
    int n = in.it();
    int c = in.it();
    int v = in.it();
    ArrayList<ArrayList<Route>> graph = new ArrayList<>();
    for(int i = 0; i < n; i++){
      graph.add(new ArrayList<>());
    }

    int[] ss = in.idx(v);
    int[] tt = in.idx(v);
    int[] ys = in.it(v);
    int[] ms = in.it(v);

    for(int i = 0; i < v; ++i){
      graph.get(ss[i]).add(new Route(tt[i], ys[i], ms[i]));
    }

    PriorityQueue<Route> queue = new PriorityQueue<>();
    queue.add(new Route(0, 0, 0));
    int[][] dp = new int[n][c + 1];
    Arrays.stream(dp).forEach(arr -> Arrays.fill(arr, INF));
    while(!queue.isEmpty()){
      Route r = queue.poll();
      if(r.cost > c || dp[r.idx][r.cost] <= r.time) continue;

      dp[r.idx][r.cost] = r.time;
      for(Route x: graph.get(r.idx)){
        queue.add(new Route(x.idx, r.cost + x.cost, r.time + x.time));
      }
    }

    int ans = INF;
    for(int x: dp[n - 1]) ans = Math.min(ans, x);
    if(ans == INF) ans = -1;

    out.println(ans);
  }

  /* consts */
  final int mod = 998244353;
  final String yes = "Yes";
  final String no = "No";

  /* input */
  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;
    }
  }

  /* output */
  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');
    }

  }
}
0