結果

問題 No.3013 ハチマキ買い星人
ユーザー InTheBloom
提出日時 2025-01-31 18:06:12
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 482 ms / 2,000 ms
コード長 1,387 bytes
コンパイル時間 5,330 ms
コンパイル使用メモリ 173,416 KB
実行使用メモリ 41,884 KB
最終ジャッジ日時 2025-01-31 18:06:32
合計ジャッジ時間 17,471 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int N, M, P;
    long Y;
    readln.read(N, M, P, Y);
    auto graph = new Tuple!(int, int)[][](N);
    foreach (i; 0 .. M) {
        int A, B, C; readln.read(A, B, C);
        A--, B--;
        graph[A] ~= tuple(B, C);
        graph[B] ~= tuple(A, C);
    }

    auto D = new int[](P);
    auto E = new int[](P);
    foreach (i; 0 .. P) {
        readln.read(D[i], E[i]);
        D[i]--;
    }

    // dijkstra
    auto pq = BinaryHeap!(Tuple!(int, long)[], "b[1] < a[1]")([]);
    auto cost = new long[](N);
    cost[] = long.max;

    cost[0] = 0;
    pq.insert(tuple(0, 0L));

    while (!pq.empty()) {
        auto pos = pq.front(); pq.removeFront();
        int u = pos[0];
        long c = pos[1];
        if (cost[u] < c) continue;

        foreach (to; graph[u]) {
            int v = to[0];
            long nc = c + to[1];

            if (nc < cost[v]) {
                cost[v] = nc;
                pq.insert(tuple(v, nc));
            }
        }
    }

    long ans = 0;
    foreach (i; 0 .. P) {
        long rem = max(0L, Y - cost[D[i]]);
        if (rem <= 0) continue;
        ans = max(ans, rem / E[i]);
    }

    writeln(ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0