結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2017-06-22 23:06:10 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 878 ms |
コンパイル使用メモリ | 111,136 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 20:26:57 |
合計ジャッジ時間 | 2,598 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
// tested by Hightail - https://github.com/dj3500/hightail import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.math, std.typecons, std.container, core.bitop; immutable inf = 10^^9 + 7; int n, c, v; int[] s, t, y, m; void main() { scan(n); scan(c); scan(v); s = readln.split.to!(int[]); t = readln.split.to!(int[]); y = readln.split.to!(int[]); m = readln.split.to!(int[]); alias Road = Tuple!(int, "to", int, "y", int, "m"); auto adj = new Road[][](n, 0); foreach (i ; 0 .. v) { adj[s[i] - 1] ~= Road(t[i] - 1, y[i], m[i]); } debug { //stderr.writeln(adj); } auto dp = new int[][](n, c + 1); foreach (i ; 0 .. n) { foreach (j ; 0 .. c + 1) { dp[i][j] = inf; } } dp[0][c] = 0; foreach (i ; 0 .. n) { foreach (j ; 0 .. c + 1) { if (dp[i][j] == inf) continue; foreach (v ; adj[i]) { if (j - v.y >= 0) dp[v.to][j - v.y] = min(dp[v.to][j - v.y], dp[i][j] + v.m); } debug { //writeln("dp:", dp); } } } int ans = dp[n - 1].minElement; if (ans == inf) { writeln(-1); } else { writeln(ans); } } void scan(T...)(ref T args) { string[] line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront(); } assert(line.empty); }