結果

問題 No.1 道のショートカット
ユーザー ohuton_laboohuton_labo
提出日時 2014-12-23 23:45:48
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,626 bytes
コンパイル時間 798 ms
コンパイル使用メモリ 78,056 KB
実行使用メモリ 6,776 KB
最終ジャッジ日時 2023-09-22 11:50:52
合計ジャッジ時間 2,413 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,396 KB
testcase_01 AC 4 ms
6,628 KB
testcase_02 AC 4 ms
6,428 KB
testcase_03 AC 4 ms
6,404 KB
testcase_04 AC 4 ms
6,480 KB
testcase_05 AC 4 ms
6,436 KB
testcase_06 AC 4 ms
6,432 KB
testcase_07 AC 4 ms
6,432 KB
testcase_08 AC 7 ms
6,588 KB
testcase_09 AC 5 ms
6,436 KB
testcase_10 WA -
testcase_11 AC 6 ms
6,676 KB
testcase_12 WA -
testcase_13 AC 9 ms
6,444 KB
testcase_14 WA -
testcase_15 AC 4 ms
6,608 KB
testcase_16 AC 5 ms
6,400 KB
testcase_17 AC 4 ms
6,484 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 5 ms
6,448 KB
testcase_21 AC 4 ms
6,472 KB
testcase_22 AC 4 ms
6,392 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 4 ms
6,488 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 4 ms
6,396 KB
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 10 ms
6,432 KB
testcase_32 WA -
testcase_33 AC 5 ms
6,428 KB
testcase_34 WA -
testcase_35 AC 5 ms
6,468 KB
testcase_36 WA -
testcase_37 AC 5 ms
6,432 KB
testcase_38 AC 4 ms
6,404 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 5 ms
6,512 KB
testcase_42 AC 4 ms
6,388 KB
testcase_43 AC 4 ms
6,568 KB
権限があれば一括ダウンロードができます

ソースコード

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 dp[51][51][301];//data[i][j][k] i:iから jに向かう時の k総コスト
int cost[51][51];//始点から終点にいくためのコスト

int main(){
	int n,c,v;
	int *flag;
	cin>>n;
	cin>>c;
	cin>>v;
	flag=new int[51];
	for(int i=0;i<51;i++){
		flag[i]=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> *data;
	data = new vector<int>[n+1];

	for(int i=0;i<51;i++){
		for(int j=0;j<51;j++){
			for(int k=0;k<301;k++){
				dp[i][j][k]=-1;
			}
		}
	}


	for(int i=0;i<v;i++){
		dp[s[i]][t[i]][y[i]]=m[i];
		dp[t[i]][s[i]][y[i]]=m[i];
		cost[s[i]][t[i]]=y[i];
		data[s[i]].push_back(t[i]);
	}
	for(int i=0;i<v;i++){
		if(dp[s[i]][t[i]][y[i]]>=m[i]){
			dp[s[i]][t[i]][y[i]]=m[i];
		}
		if(dp[t[i]][s[i]][y[i]]>=m[i]){
			dp[t[i]][s[i]][y[i]]=m[i];
		}
		if(cost[s[i]][t[i]]>=y[i]){
			cost[s[i]][t[i]]=y[i];
		}
	}
	for(int i=1;i<=n;i++){
		data[i].push_back(1);
	}

	queue<int> q;

	for(int i=0;i<data[1].size();i++){
		q.push(data[1].at(i));
	}
	flag[1]=1;

	while(q.size()!=0){
		int top=q.front();
		//cout<<"top="<<top<<endl;
		q.pop();
		for(int i=0;i<data[top].size();i++){
			if(data[top].at(i)==1)continue;
			if(flag[data[top].at(i)]==0){
				q.push(data[top].at(i));
				flag[data[top].at(i)]=1;
			}
			for(int j=0;j<=c;j++){
				if(dp[1][top][j]>-1&&j+cost[top][data[top].at(i)]<=c){
					int tmp = dp[1][top][j]+dp[top][data[top].at(i)][cost[top][data[top].at(i)]];
					if(dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]==-1||
						dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]>=tmp){
						dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]=tmp;
					}
				}
			}
		}
	}

	for(int i=0;i<data[1].size();i++){
		q.push(data[1].at(i));
	}
	for(int i=0;i<51;i++){
		flag[i]=0;
	}
	flag[1]=1;

	while(q.size()!=0){
		int top=q.front();
		//cout<<"top="<<top<<endl;
		q.pop();
		for(int i=0;i<data[top].size();i++){
			if(data[top].at(i)==1)continue;
			if(flag[data[top].at(i)]==0){
				q.push(data[top].at(i));
				flag[data[top].at(i)]=1;
			}
			for(int j=0;j<=c;j++){
				if(dp[1][top][j]>-1&&j+cost[top][data[top].at(i)]<=c){
					int tmp = dp[1][top][j]+dp[top][data[top].at(i)][cost[top][data[top].at(i)]];
					if(dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]==-1||
						dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]>=tmp){
						dp[1][data[top].at(i)][j+cost[top][data[top].at(i)]]=tmp;
					}
				}
			}
		}
	}
	int min1=10000000;

	for(int i=0;i<=c;i++){
		//cout<<dp[1][n][i]<<endl;
		if(min1>=dp[1][n][i]&&dp[1][n][i]>-1)min1 = dp[1][n][i];
	}

	if(min1==10000000){
		cout<<-1<<endl;
	}
	else{
		cout<<min1<<endl;
	}
	return 0;
}
0