結果

問題 No.1 道のショートカット
ユーザー naimonon77
提出日時 2016-01-14 01:04:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,716 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 67,160 KB
実行使用メモリ 10,400 KB
最終ジャッジ日時 2024-07-08 04:22:07
合計ジャッジ時間 10,301 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <time.h>
#include <cstdio>
#include <vector>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int test = 0;
typedef struct root {
  int nextCity;
  int money;
  int time;
}Root;
struct town {
  vector<Root> root;
};

int N,C,V;
int S[1505];
int T[1505];
int Y[1505];
int M[1505];
struct town town[55];
int minTime = INT_MAX;
void min_money(int currentTown,int balance,int totalTime) {
  int i,j,k,l;
  int n = town[currentTown].root.size();
  if(N == currentTown) {
    if(minTime > totalTime) minTime = totalTime;
    return;
  }
  for(i=0;i<n;i++) {
    if(balance+1 > town[currentTown].root[i].money) {
      min_money(town[currentTown].root[i].nextCity
      ,balance-town[currentTown].root[i].money 
      ,totalTime + town[currentTown].root[i].time);
    }
  }
}
int main(void)
{
  int i,j,k,l;
  cin >> N >> C >> V;
  /*
  for(i=0;i<20;i++) {
  printf("town[%d].root.size() = %d\n",i,town[i].root.size());
  } */
  rep(i,V) {
    cin >> S[i];
  }
  rep(i,V) {
    cin >> T[i];
  }
  rep(i,V) {
    cin >> Y[i];
  }
  rep(i,V) {
    cin >> M[i];
  }

  rep(i,V) {
    Root tmp = {T[i],Y[i],M[i]};
    town[S[i]].root.push_back(tmp);
  }
  min_money(1,C,0);
  if(minTime == INT_MAX) minTime = -1;
  printf("%d\n",minTime);
  /*
  rep(i,N) {
    rep(j,town[i].root.size()) {
      printf("%d",i);
      printf(" %d",town[i].root[j].nextCity);
      printf(" %d",town[i].root[j].money);
      printf(" %d\n",town[i].root[j].time);
    }
  }
  */
  return 0;
}
0