結果
| 問題 | No.1 道のショートカット |
| ユーザー |
 C++
|
| 提出日時 | 2024-06-18 02:09:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 40 |
ソースコード
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 contributionsthis.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');}}}