結果

問題 No.1 道のショートカット
ユーザー ohuton_laboohuton_labo
提出日時 2014-12-23 18:43:48
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,779 bytes
コンパイル時間 545 ms
コンパイル使用メモリ 69,192 KB
実行使用メモリ 10,272 KB
最終ジャッジ日時 2024-07-08 03:39:26
合計ジャッジ時間 7,142 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 WA -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>

int max(int a,int b){
	if(a>=b)return a;
	else return b;
}


void swap(int *a,int *b){
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void babbleSort(int *data,int n){
	for(int i=0;i<n;i++){
		for(int j=n-1;j>i;j--){
			if(data[j]>=data[j-1]){
				swap(&data[j],&data[j-1]);
			}
		}
	}
}


using namespace std;

/*
cin.ignore();
	getline(cin,dataStr);
	data = new int[n];
	stringToInteger(&dataStr,data,n);
*/

void stringToInteger(string *str,int *data,int n){
	for(int i=0;i<n;i++){
		int spaceN = str->find(' ',0);

		data[i] = atoi(str->substr(0,spaceN).c_str());
		str->erase(0,spaceN+1);
	}
}

int data[1501][1501][2];//data[i][j][k] i:iから jに向かう時の k:0コスト 1:	時間
int min1;
int flag;

void solve(int *s,int *t,int c,int n,int v,int now,int time1){
	if(c<0)return;

	if(now==n){
		if(min1>=time1){
			min1=time1;
			flag=1;
		}
	}
	else if(now>n)return;
	else{
		for(int i=0;i<v;i++){
			if(s[i]==now){
				solve(s,t,c-data[s[i]][t[i]][0],n,v,t[i],time1+data[s[i]][t[i]][1]);
			}
		}
	}
}

int main(){
	int n,c,v;
	cin>>n;
	cin>>c;
	cin>>v;
	min1=10000000;
	flag=0;

	int *s,*t,*y,*m;
	s = new int[v];
	t = new int[v];
	y = new int[v];
	m =  new int[v];

	string str;
	cin.ignore();
	getline(cin,str);
	stringToInteger(&str,s,v);
	getline(cin,str);
	stringToInteger(&str,t,v);
	getline(cin,str);
	stringToInteger(&str,y,v);
	getline(cin,str);
	stringToInteger(&str,m,v);

	vector<int> *p;
	p = new vector<int> [v];


	for(int i=0;i<v;i++){
		data[s[i]][t[i]][0]=y[i];
		data[s[i]][t[i]][1]=m[i];
	}
	solve(s,t,c,n,v,1,0);
	if(flag==0){
		cout<<-1<<endl;
	}
	else{
		cout<<min1<<endl;
	}
}
0