結果
問題 | No.496 ワープクリスタル (給料日前編) |
ユーザー |
![]() |
提出日時 | 2019-04-04 14:47:26 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 4,334 bytes |
コンパイル時間 | 552 ms |
コンパイル使用メモリ | 32,000 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 23:02:17 |
合計ジャッジ時間 | 1,624 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_SIZE_MAX 105 // 最大サイズ#define D_CRS_MAX 55 // 最大クリスタル数// 内部構造体 - クリスタル情報typedef struct Crs {int miX, miY; // 移動距離int miVal; // 値段double mdCost; // コスパ} Crs;// 内部変数static FILE *szpFpI; // 入力static int siGx, siGy; // 目的地static Crs sz1Crs[D_CRS_MAX]; // クリスタルstatic int siCCnt; // クリスタル数static int siCost; // 通行料static int si3Sum[D_CRS_MAX][D_SIZE_MAX][D_SIZE_MAX]; // コスト合計[クリスタル][位置X][位置Y]static int siMin; // 最小コスト// 内部変数 - テスト用#ifdef D_TESTstatic int siRes;static FILE *szpFpA;static int siTNo;#endif// 出力intfOut(char *pcpLine // <I> 1行){char lc1Buf[1024];#ifdef D_TESTfgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, pcpLine)) {siRes = -1;}#elseprintf("%s", pcpLine);#endifreturn 0;}// ソート関数 - コスパ降順intfSortFnc(const void *pzpVal1 // <I> 値1, const void *pzpVal2 // <I> 値2){Crs *lzpVal1 = (Crs *)pzpVal1;Crs *lzpVal2 = (Crs *)pzpVal2;// コスパ降順if (lzpVal1->mdCost > lzpVal2->mdCost) {return -1;}else if (lzpVal1->mdCost < lzpVal2->mdCost) {return 1;}return 0;}// コスト合計 - セットintfSetSum(int piCNo // <I> クリスタル 0~, int piX // <I> 位置X, int piY // <I> 位置Y, int piSum // <I> コスト合計){// 範囲チェックif (piX > siGx) {return 0;}if (piY > siGy) {return 0;}// コスト合計if (si3Sum[piCNo][piX][piY] > 0) {if (si3Sum[piCNo][piX][piY] <= piSum) {return 0;}}si3Sum[piCNo][piX][piY] = piSum;// 最小コストif (siMin > piSum) {siMin = piSum;}// 選択中if (piCNo < siCCnt) {// 選択int liSum = piSum - (sz1Crs[piCNo].miX + sz1Crs[piCNo].miY) * siCost + sz1Crs[piCNo].miVal;fSetSum(piCNo + 1, piX + sz1Crs[piCNo].miX, piY + sz1Crs[piCNo].miY, liSum);// 選択なしfSetSum(piCNo + 1, piX, piY, piSum);}return 0;}// 実行メインintfMain(){int i;char lc1Buf[1024];// 目的地・クリスタル数・通行料 - 取得int liCCnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d%d%d", &siGx, &siGy, &liCCnt, &siCost);// クリスタル - 取得for (i = 0; i < liCCnt; i++) {fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d%d", &sz1Crs[siCCnt].miX, &sz1Crs[siCCnt].miY, &sz1Crs[siCCnt].miVal);// コスパsz1Crs[siCCnt].mdCost = (double)sz1Crs[siCCnt].miVal / (double)(sz1Crs[siCCnt].miX + sz1Crs[siCCnt].miY);if (sz1Crs[siCCnt].mdCost < (double)siCost) {siCCnt++;}}// クリスタル - ソートqsort(sz1Crs, siCCnt, sizeof(Crs), fSortFnc);// コスト合計 - セットint liSum = (siGx + siGy) * siCost;fSetSum(0, 0, 0, liSum);return 0;}// 1回実行intfOne(){int liRet;char lc1Buf[1024];// データ - 初期化siCCnt = 0; // クリスタル数memset(si3Sum, 0, sizeof(si3Sum)); // コスト合計siMin = INT_MAX; // 最小コスト// 入力 - セット#ifdef D_TESTsprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);szpFpI = fopen(lc1Buf, "r");sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);szpFpA = fopen(lc1Buf, "r");siRes = 0;#elseszpFpI = stdin;#endif// 実行メインliRet = fMain();// 結果 - セットsprintf(lc1Buf, "%d\n", siMin);// 結果 - 出力fOut(lc1Buf);// 残データ有無#ifdef D_TESTlc1Buf[0] = '\0';fgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, "")) {siRes = -1;}#endif// テストファイルクローズ#ifdef D_TESTfclose(szpFpI);fclose(szpFpA);#endif// テスト結果#ifdef D_TESTif (siRes == 0) {printf("OK %d\n", siTNo);}else {printf("NG %d\n", siTNo);}#endifreturn 0;}// プログラム開始intmain(){#ifdef D_TESTint i;for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {siTNo = i;fOne();}#elsefOne();#endifreturn 0;}