結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー akakimidori
提出日時 2018-07-08 02:13:35
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 931 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 307 ms
コンパイル使用メモリ 40,416 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-01 16:11:07
合計ジャッジ時間 1,352 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define POS(i,j) ((i)*n+(j))

void run(void){
  int n;
  scanf("%d",&n);
  int s[50];
  int i,j,k;
  for(i=0;i<n;i++) scanf("%d",s+i);
  int m;
  scanf("%d",&m);
  const int inf=100000;
  int c[2500];
  for(i=0;i<n;i++) for(j=0;j<n;j++) c[POS(i,j)]=(i==j)?0:inf;
  for(i=0;i<m;i++){
    int a,b,cc;
    scanf("%d%d%d",&a,&b,&cc);
    c[POS(a,b)]=cc;
    c[POS(b,a)]=cc;
  }
  for(k=0;k<n;k++){
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	c[POS(i,j)]=MIN(c[POS(i,j)],c[POS(i,k)]+c[POS(k,j)]);
      }
    }
  }
  int min=inf;
  for(i=1;i<n-1;i++){
    for(j=1;j<n-1;j++){
      if(i==j) continue;
      min=MIN(min,c[POS(0,i)]+s[i]+c[POS(i,j)]+s[j]+c[POS(j,n-1)]);
    }
  }
  printf("%d\n",min);
}

int main(void){
  run();
  return 0;
}
0