結果

問題 No.1 道のショートカット
コンテスト
ユーザー scholardream
提出日時 2026-05-30 23:54:03
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,486 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,662 ms
コンパイル使用メモリ 40,308 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-30 23:54:08
合計ジャッジ時間 3,613 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1e9
#define MAXN 55
#define MAXC 305
int min(int a, int b) {
    return a < b ? a : b;
}

int main() {
    int N, C, V;
    scanf("%d", &N);
    scanf("%d", &C);
    scanf("%d", &V);
    int *S = (int*)malloc(V * sizeof(int));
    int *T = (int*)malloc(V * sizeof(int));
    int *Y = (int*)malloc(V * sizeof(int));
    int *M = (int*)malloc(V * sizeof(int));
    for (int i = 0; i < V; i++) scanf("%d", &S[i]);
    for (int i = 0; i < V; i++) scanf("%d", &T[i]);
    for (int i = 0; i < V; i++) scanf("%d", &Y[i]);
    for (int i = 0; i < V; i++) scanf("%d", &M[i]);
    int dp[MAXN][MAXC];
    for (int i = 1; i <= N; i++) {
        for (int c = 0; c <= C; c++) {
            dp[i][c] = INF;
        }
    }
    dp[1][0] = 0;
    for (int u = 1; u <= N; u++) {
        for (int c = 0; c <= C; c++) {
            if (dp[u][c] == INF) continue;
            for (int i = 0; i < V; i++) {
                if (S[i] != u) continue;
                int v = T[i];
                int y = Y[i];
                int m = M[i];
                int newc = c + y;
                if (newc <= C) {
                    dp[v][newc] = min(dp[v][newc], dp[u][c] + m);
                }
            }
        }
    }
    int ans = INF;
    for (int c = 0; c <= C; c++) {
        ans = min(ans, dp[N][c]);
    }

    if (ans == INF) printf("-1\n");
    else printf("%d\n", ans);

    free(S); free(T); free(Y); free(M);
    return 0;
}
0