結果
問題 | No.1 道のショートカット |
ユーザー | 綾地寧々 |
提出日時 | 2015-05-15 08:36:24 |
言語 | C90 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,827 bytes |
コンパイル時間 | 781 ms |
コンパイル使用メモリ | 24,408 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-27 21:44:11 |
合計ジャッジ時間 | 2,389 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
4,380 KB |
testcase_01 | AC | 0 ms
4,380 KB |
testcase_02 | AC | 0 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 0 ms
4,376 KB |
testcase_06 | AC | 0 ms
4,380 KB |
testcase_07 | AC | 0 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 1 ms
4,376 KB |
testcase_14 | AC | 0 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 0 ms
4,376 KB |
testcase_17 | AC | 0 ms
4,376 KB |
testcase_18 | AC | 1 ms
4,380 KB |
testcase_19 | AC | 0 ms
4,376 KB |
testcase_20 | AC | 0 ms
4,380 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 1 ms
4,376 KB |
testcase_24 | AC | 1 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 1 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,384 KB |
testcase_31 | AC | 1 ms
4,380 KB |
testcase_32 | AC | 1 ms
4,376 KB |
testcase_33 | AC | 1 ms
4,376 KB |
testcase_34 | AC | 2 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 1 ms
4,376 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 1 ms
4,380 KB |
testcase_39 | AC | 1 ms
4,380 KB |
testcase_40 | AC | 1 ms
4,376 KB |
testcase_41 | AC | 1 ms
4,376 KB |
testcase_42 | AC | 0 ms
4,376 KB |
testcase_43 | AC | 1 ms
4,380 KB |
ソースコード
#include <stdio.h> #define min(x,y) ((x)<(y) ? (x) : (y)) int main(void); int move(int start, int money, int time, int maxtime); int g_towns = 0; int g_money = 0; int g_roads = 0; int g_departure[1500] = {0}; int g_arrival[1500] = {0}; int g_cost[1500] = {0}; int g_time[1500] = {0}; int main(void) { char temp[5]; int i, ret; scanf("%d", &g_towns); scanf("%d", &g_money); scanf("%d", &g_roads); for ( i=0; i<g_roads; i++ ) { scanf("%d", &g_departure[i]); } for ( i=0; i<g_roads; i++ ) { scanf("%d", &g_arrival[i]); } for ( i=0; i<g_roads; i++ ) { scanf("%d", &g_cost[i]); } for ( i=0; i<g_roads; i++ ) { scanf("%d", &g_time[i]); } ret = move(1,g_money,0,-1); printf("%d\n", ret); return 0; } int move(int start, int money, int time, int maxtime) { int mintime = -1; int newtime = 0; int index = 0; /* ----- 再帰呼出し終了条件の判定 ---------- */ /* コストが最大値を超えてしまった場合 */ if ( money < 0 ) { return -1; } /* 最後の街に到着した場合 */ else if ( start == g_towns ) { return time; } /* 他のルートより時間がかかったことを検出した場合 */ else if ( (maxtime != -1) && (maxtime <= time) ) { return -1; } /* ----- 再帰呼出しをおこなう ------------ */ mintime = maxtime; for ( index=0; index<g_roads; index++ ) { /* 行き先が見つかった */ if ( g_departure[index] == start ) { newtime = move(g_arrival[index],money-g_cost[index],time+g_time[index],mintime); if ( newtime == -1 ) { /* 今回のルートでは最後まで辿りつけなかったので何もしない。 */ } else if ( mintime == -1 ) { mintime = newtime; } else { mintime = min(mintime, newtime); } } } /* ----- 探した最短時間での結果を返却する */ return mintime; }