Submission #8091419
Source Code Expand
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_VTX_MAX 100005 // 最大頂点数
#define D_EDGE_MAX 100000 // 最大辺数
// 内部構造体 - 辺情報
typedef struct Edge {
int miVNo; // 接続先頂点
int miLen; // 距離
struct Edge *mzpNext; // 次の辺情報
} Edge;
// 内部構造体 - 頂点情報
typedef struct Vtx {
Edge *mzpEdge; // 辺
int miMin; // 最短距離
int miQNo; // クエリ番号
} Vtx;
// 内部変数
static FILE *szpFpI; // 入力
static Vtx sz1Vtx[D_VTX_MAX]; // 頂点
static int siVCnt; // 頂点数
static Edge sz1Edge[D_EDGE_MAX]; // 辺
static int siECnt; // 辺数
static int si1Min[D_VTX_MAX]; // 最短距離[クエリ]
// 内部変数 - テスト用
#ifdef D_TEST
static int siRes;
static FILE *szpFpA;
static int siTNo;
#endif
// 1行出力
int
fOutLine(
char *pcpLine // <I> 1行
)
{
char lc1Buf[1024];
#ifdef D_TEST
fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
if (strcmp(lc1Buf, pcpLine)) {
siRes = -1;
}
#else
printf("%s", pcpLine);
#endif
return 0;
}
// 辺 - 追加
int
fAddEdge(
int piVFNo // <I> 頂点 - 元 0~
, int piVTNo // <I> 頂点 - 先 0~
, int piLen // <I> 距離
)
{
sz1Edge[siECnt].miVNo = piVTNo;
sz1Edge[siECnt].miLen = piLen;
sz1Edge[siECnt].mzpNext = sz1Vtx[piVFNo].mzpEdge;
sz1Vtx[piVFNo].mzpEdge = &sz1Edge[siECnt];
siECnt++;
return 0;
}
// ソート関数 - クエリ番号降順
int
fSortFnc(
const void *pzpVal1 // <I> 値1
, const void *pzpVal2 // <I> 値2
)
{
Vtx *lzpVal1 = (Vtx *)pzpVal1;
Vtx *lzpVal2 = (Vtx *)pzpVal2;
// クエリ番号降順
if (lzpVal1->miQNo > lzpVal2->miQNo) {
return -1;
}
else if (lzpVal1->miQNo < lzpVal2->miQNo) {
return 1;
}
return 0;
}
// 最短距離 - セット
int
fSetMin(
int piVNo // <I> 頂点
, int piLen // <I> 最短距離
)
{
Edge *lzpEdge = sz1Vtx[piVNo].mzpEdge;
if (lzpEdge == NULL) { // 葉
// 最短距離 - セット
sz1Vtx[piVNo].miMin = piLen;
}
else { // 親
// 辺でループ
while (lzpEdge != NULL) {
// 下位へ
fSetMin(lzpEdge->miVNo, piLen + lzpEdge->miLen);
// 次の辺へ
lzpEdge = lzpEdge->mzpNext;
}
}
return 0;
}
// クエリ番号 - セット
int
fSetQNo(
int piVNo // <I> 頂点
, int piQNo // <I> クエリ番号
)
{
// セット済
if (sz1Vtx[piVNo].miQNo < INT_MAX) {
return 0;
}
sz1Vtx[piVNo].miQNo = piQNo;
// 辺でループ
Edge *lzpEdge = sz1Vtx[piVNo].mzpEdge;
while (lzpEdge != NULL) {
// 下位へ
fSetQNo(lzpEdge->miVNo, piQNo);
// 次の辺へ
lzpEdge = lzpEdge->mzpNext;
}
return 0;
}
// 実行メイン
int
fMain(
)
{
int i;
char lc1Buf[1024];
// 頂点数・クエリ数 - 取得
int liQCnt;
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d%d", &siVCnt, &liQCnt);
// 辺 - 取得
int liVNo, liLen;
for (i = 0; i < siVCnt - 1; i++) {
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d%d", &liVNo, &liLen);
// 辺 - 追加
fAddEdge(liVNo, i + 2, liLen);
}
// 頂点 - 初期化
for (i = 1; i <= siVCnt; i++) {
sz1Vtx[i].miMin = INT_MAX;
sz1Vtx[i].miQNo = INT_MAX;
}
// 最短距離 - セット
fSetMin(1, 0);
// クエリ - 取得
for (i = 1; i <= liQCnt; i++) {
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
sscanf(lc1Buf, "%d", &liVNo);
// クエリ番号 - セット
fSetQNo(liVNo, i);
}
// 頂点 - ソート
qsort(sz1Vtx, siVCnt + 1, sizeof(Vtx), fSortFnc);
// 最短距離[クエリ] - セット
liVNo = 0;
si1Min[liQCnt + 1] = INT_MAX;
for (i = liQCnt; i > 0; i--) {
si1Min[i] = si1Min[i + 1];
// 最短距離[クエリ] - 更新
while (sz1Vtx[liVNo].miQNo > i) {
if (si1Min[i] > sz1Vtx[liVNo].miMin) {
si1Min[i] = sz1Vtx[liVNo].miMin;
}
liVNo++;
}
}
// 出力
for (i = 1; i <= liQCnt; i++) {
if (si1Min[i] == INT_MAX) {
sprintf(lc1Buf, "-1\n");
}
else {
sprintf(lc1Buf, "%d\n", si1Min[i]);
}
fOutLine(lc1Buf);
}
return 0;
}
// 1回実行
int
fOne(
)
{
int liRet;
char lc1Buf[1024];
// データ - 初期化
memset(sz1Vtx, 0, sizeof(sz1Vtx)); // 頂点
siECnt = 0; // 辺数
// 入力 - セット
#ifdef D_TEST
sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
szpFpI = fopen(lc1Buf, "r");
sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
szpFpA = fopen(lc1Buf, "r");
siRes = 0;
#else
szpFpI = stdin;
#endif
// 実行メイン
liRet = fMain();
// 残データ有無
#ifdef D_TEST
lc1Buf[0] = '\0';
fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
if (strcmp(lc1Buf, "")) {
siRes = -1;
}
#endif
// テストファイルクローズ
#ifdef D_TEST
fclose(szpFpI);
fclose(szpFpA);
#endif
// テスト結果
#ifdef D_TEST
if (siRes == 0) {
printf("OK %d\n", siTNo);
}
else {
printf("NG %d\n", siTNo);
}
#endif
return 0;
}
// プログラム開始
int
main()
{
#ifdef D_TEST
int i;
for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
siTNo = i;
fOne();
}
#else
fOne();
#endif
return 0;
}
Submission Info
Submission Time
2019-10-23 10:02:42+0900
Task
C - 山登り(Mountain Climbing)
User
asugen0402
Language
C (GCC 5.4.1)
Score
1000
Code Size
5522 Byte
Status
AC
Exec Time
67 ms
Memory
7676 KB
Compile Error
./Main.c: In function ‘fMain’:
./Main.c:166:2: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
^
./Main.c:172:3: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
^
./Main.c:190:3: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
^
Judge Result
Set Name
subtask1
all
Score / Max Score
1 / 1
999 / 999
Status
Set Name
Test Cases
subtask1
sample/sample.txt, subtask1/1.txt, subtask1/2.txt, subtask1/3.txt, subtask1/4.txt, subtask1/5.txt, subtask1/6.txt, subtask1/ad1.txt, subtask1/ad2.txt, subtask1/ad3.txt, subtask1/ad4.txt, subtask1/ad5.txt, subtask1/ad6.txt
all
sample, subtask1, subtask2, sample/sample.txt, subtask1/1.txt, subtask1/2.txt, subtask1/3.txt, subtask1/4.txt, subtask1/5.txt, subtask1/6.txt, subtask1/ad1.txt, subtask1/ad2.txt, subtask1/ad3.txt, subtask1/ad4.txt, subtask1/ad5.txt, subtask1/ad6.txt, subtask2/10.txt, subtask2/11.txt, subtask2/12.txt, subtask2/13.txt, subtask2/14.txt, subtask2/15.txt, subtask2/16.txt, subtask2/17.txt, subtask2/18.txt, subtask2/19.txt, subtask2/20.txt, subtask2/21.txt, subtask2/22.txt, subtask2/23.txt, subtask2/24.txt, subtask2/25.txt, subtask2/7.txt, subtask2/8.txt, subtask2/9.txt, subtask2/octopus.txt, subtask2/octopus_2.txt
Case Name
Status
Exec Time
Memory
sample/sample.txt
AC
3 ms
1920 KB
subtask1/1.txt
AC
1 ms
1792 KB
subtask1/2.txt
AC
1 ms
1792 KB
subtask1/3.txt
AC
2 ms
1792 KB
subtask1/4.txt
AC
2 ms
1792 KB
subtask1/5.txt
AC
2 ms
1792 KB
subtask1/6.txt
AC
2 ms
1792 KB
subtask1/ad1.txt
AC
2 ms
1792 KB
subtask1/ad2.txt
AC
2 ms
1792 KB
subtask1/ad3.txt
AC
2 ms
1792 KB
subtask1/ad4.txt
AC
2 ms
1792 KB
subtask1/ad5.txt
AC
2 ms
1792 KB
subtask1/ad6.txt
AC
2 ms
1792 KB
subtask2/10.txt
AC
46 ms
4860 KB
subtask2/11.txt
AC
64 ms
4860 KB
subtask2/12.txt
AC
61 ms
4860 KB
subtask2/13.txt
AC
61 ms
4860 KB
subtask2/14.txt
AC
66 ms
4860 KB
subtask2/15.txt
AC
60 ms
4860 KB
subtask2/16.txt
AC
66 ms
4860 KB
subtask2/17.txt
AC
64 ms
4860 KB
subtask2/18.txt
AC
67 ms
4860 KB
subtask2/19.txt
AC
64 ms
4860 KB
subtask2/20.txt
AC
66 ms
4860 KB
subtask2/21.txt
AC
67 ms
4860 KB
subtask2/22.txt
AC
64 ms
4860 KB
subtask2/23.txt
AC
64 ms
4860 KB
subtask2/24.txt
AC
57 ms
5116 KB
subtask2/25.txt
AC
47 ms
7676 KB
subtask2/7.txt
AC
6 ms
2044 KB
subtask2/8.txt
AC
7 ms
2044 KB
subtask2/9.txt
AC
46 ms
4860 KB
subtask2/octopus.txt
AC
47 ms
6396 KB
subtask2/octopus_2.txt
AC
47 ms
6396 KB