結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー mudbdb
提出日時 2015-07-12 17:42:08
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 2,054 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 23,168 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 01:23:45
合計ジャッジ時間 1,038 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
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