結果

問題 No.17 2つの地点に泊まりたい
ユーザー mudbdbmudbdb
提出日時 2015-07-12 17:42:08
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 2,054 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 23,424 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-23 02:05:40
合計ジャッジ時間 997 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 0 ms
6,940 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 0 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 0 ms
6,944 KB
testcase_20 AC 0 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:47:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   47 |   scanf("%d", &N);
      |   ^~~~~~~~~~~~~~~
main.c:50:23: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |   for (i=0; i<N; i++) scanf("%d", &(S[i]));
      |                       ^~~~~~~~~~~~~~~~~~~~
main.c:51:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |   scanf("%d", &M);
      |   ^~~~~~~~~~~~~~~
main.c:56:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |     scanf("%d", &(A[i]));
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:57:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |     scanf("%d", &(B[i]));
      |     ^~~~~~~~~~~~~~~~~~~~
main.c:58:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf("%d", &(C[i]));
      |     ^~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
int min(int **pathcost, int i, int j, int k)
{
  int min;
  if (pathcost[i][j] == -1) {
    if ((pathcost[i][k] == -1) || (pathcost[k][j] == -1)) {
      min = -1;
    } else {
      min = pathcost[i][k] + pathcost[k][j];
    }
  } else {
    if ((pathcost[i][k] == -1) || (pathcost[k][j] == -1)) {
      min = pathcost[i][j];
    } else {
      if (pathcost[i][j] < (pathcost[i][k] + pathcost[k][j])) {
        min = pathcost[i][j];
      } else {
        min = pathcost[i][k] + pathcost[k][j];
      }
    }
  }
  return min;
}
int total(int **pathcost, int *S, int i, int j, int N)
{
  int total;
  if ((pathcost[0][i] == -1)||
      (pathcost[i][j] == -1)||
      (pathcost[j][N-1] == -1)) {
    total = -1;
  } else {
    total = pathcost[0][i] + S[i] 
          + pathcost[i][j] + S[j]
          + pathcost[j][N-1];
  }
  return total;
}
int main()
{
  int N;
  int *S;
  int M;
  int *A;
  int *B;
  int *C;
  scanf("%d", &N);
  S = (int*)malloc(sizeof(int)*N);
  int i;
  for (i=0; i<N; i++) scanf("%d", &(S[i]));
  scanf("%d", &M);
  A = (int*)malloc(sizeof(int)*M);
  B = (int*)malloc(sizeof(int)*M);
  C = (int*)malloc(sizeof(int)*M);
  for (i=0; i<M; i++) {
    scanf("%d", &(A[i]));
    scanf("%d", &(B[i]));
    scanf("%d", &(C[i]));
  }

  int **pathcost;
  pathcost = (int**)malloc(sizeof(int*)*N);
  pathcost[0] = (int*)malloc(sizeof(int)*N*N);
  for (i=0; i<N*N; i++) pathcost[0][i] = -1;
  for (i=1; i<N; i++) pathcost[i] = &(pathcost[i-1][N]);
  for (i=0; i<N; i++) pathcost[i][i] = 0;
  for (i=0; i<M; i++) {
    pathcost[A[i]][B[i]] = C[i];
    pathcost[B[i]][A[i]] = C[i];
  }

  int j, k;
  for (k=0; k<N; k++)
    for (i=0; i<N; i++)
      for (j=0; j<N; j++)
        pathcost[i][j] = min(pathcost, i, j, k);

  int cost;
  int min = ~(1 << 31);
  for (i=1; i<N-1; i++)
    for (j=1; j<N-1; j++) {
      if (i != j) {
        cost = total(pathcost, S, i, j, N);
        if ((cost != -1) && (cost < min)) {
          min = cost;
        }
      }
    }

  printf("%d\n", min);
  return 0;
}
0