結果

問題 No.1 道のショートカット
ユーザー C++
提出日時 2024-02-20 17:55:19
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 5,561 bytes
コンパイル時間 4,517 ms
コンパイル使用メモリ 91,696 KB
実行使用メモリ 53,484 KB
最終ジャッジ日時 2024-09-29 03:47:30
合計ジャッジ時間 8,797 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 22 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.sql.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.function.IntFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
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(){}
  void solve(){
    int n = in.it(), c = in.it(), v = in.it();
    int[] ss = in.it(v);
    int[] tt = in.it(v);
    int[] ys = in.it(v);
    int[] ms = in.it(v);
    List<int[]> [] g = new List[n];
    for(int i = 0; i < n; ++i) g[i] = new ArrayList<>();
    for(int i = 0; i < v; ++i){
      g[ss[i] - 1].add(new int[] {tt[i] - 1, ys[i], ms[i]});
    }
    int [][] cost = new int[n][c + 1];
    final int INF = Integer.MAX_VALUE;
    Arrays.stream(cost).forEach(row -> Arrays.fill(row, INF));
    cost[0][c] = 0;
    Deque<int[]> que = new ArrayDeque<>(Arrays.asList(new int[] {c, 0}));
    while(!que.isEmpty()){
      int cc = que.peekFirst()[0];
      int s = que.pollFirst()[1];
      for(int[] gg: g[s]){
        int u = gg[0];
        int y = gg[1];
        int m = gg[2];
        if(c >= y && cost[u][c - y] > cost[s][cc] + m){
          cost[u][c - y] = cost[s][cc] + m;
          que.addLast(new int[]{c - y, u});
        }
      }
    }
    int ans = Arrays.stream(cost[n - 1]).min().getAsInt();
    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');
    }
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0