結果

問題 No.1 道のショートカット
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-01 23:25:39
言語 Fix
(1.6.0 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 12 ms / 5,000 ms
+ 22µs
コード長 1,400 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,692 ms
コンパイル使用メモリ 670,556 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2026-11-01 23:25:58
合計ジャッジ時間 16,080 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
make: 'lib.o' は更新済みです.

ソースコード

diff #
raw source code 

module Main;

import BinaryHeap;
import BoolArray;
import CPLib.Arithmetic;
import CPLib.DSegtree;
import CPLib.Graph;
import CPLib.IO;
import CPLib.LDSegtree;
import CPLib.UnionFind;
import CPLib.ZP;
import HashMap;
import HashSet;

main : IO () = (
    let n = *read_i;
    let c = *read_i;
    let v = *read_i;
    let ss = *read_is(v);
    let ss = ss.map(|x| x - 1);
    let ts = *read_is(v);
    let ts = ts.map(|x| x - 1);
    let ys = *read_is(v);
    let ms = *read_is(v);

    let encode = |vertex, money| (
        vertex * (c+1) + money
    );
    let decode = |i| (
        (i / (c+1), i % (c+1))
    );

    let graph = GraphBuilder::create(n*(c+1));
    let graph = range(0, v).fold(graph, |vi, graph|
        let s = ss.@(vi);
        let t = ts.@(vi);
        let y = ys.@(vi);
        let m = ms.@(vi);
        range(0, c+1).fold(graph, |money, graph|
            if money < y { graph };
            let s_money = money;
            let t_money = money - y;
            let s = encode(s, s_money);
            let t = encode(t, t_money);
            graph.add_edge(s, t, m)
        )
    );
    let graph = graph.build;
    let levels = graph.dijkstra(encode(0, c));
    let ans = range(0, c+1).map(|money|
        let i = encode(n-1, money);
        levels.@(i)
    ).fold(I64::maximum, min);
    let ans = if ans == I64::maximum { -1 } else { ans };
    println(ans.to_string)
);
0