結果

問題 No.1 道のショートカット
ユーザー 158b158b
提出日時 2015-05-17 18:13:36
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,248 bytes
コンパイル時間 466 ms
コンパイル使用メモリ 64,340 KB
実行使用メモリ 8,752 KB
最終ジャッジ日時 2023-09-22 12:14:31
合計ジャッジ時間 7,351 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 TLE -
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 <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <utility>
using namespace std;

//dynamic programming!
int max_city;
int max_money;
int max_road;
int from[1500];	//from * 60 + to基準ソート
int to[1500];
int costd[1500];
int timed[1500];
int table[50+1][300+1];
int mind;
//縦city 横cost

//デフォルト昇順
void combsort(int max){
	bool flg;
	int h;
	
	h = max / 1.3;
	while(true){
		flg = true;
		
		for(int i=0; i+h<max; i++){
			if(from[i] * 60 + to[i] > from[i+h] * 60 + to[i+h]){		//ソート基準変更位置
				//swap
				swap(from[i], from[i+h]);
				swap(to[i], to[i+h]);
				swap(costd[i], costd[i+h]);
				swap(timed[i], timed[i+h]);
				
				flg = false;
			}
		}
		
		if(h == 1){
			if(flg){
				break;
			}
		}else{
			h /= 1.3;
		}
	}
}

int main(){
	cin >> max_city >> max_money >> max_road;
	
	for(int i=0; i<max_road; i++){
		cin >> from[i];
	}
	for(int i=0; i<max_road; i++){
		cin >> to[i];
	}
	for(int i=0; i<max_road; i++){
		cin >> costd[i];
	}
	for(int i=0; i<max_road; i++){
		cin >> timed[i];
	}
	
	//初期化
	for(int iy=0; iy<=50; iy++){
		for(int ix=0; ix<=300; ix++){
			if(iy <= 1){
				table[iy][ix] = 0;
			}else{
				table[iy][ix] = 99999;
			}
		}
	}
	
	//道データソート！
	combsort(max_road);
	
	//dynamic programming(1→iyまで行く)
	//縦city 横cost
	for(int iy=1; iy<=max_city; iy++){		//city
		//ルート検索初期化
		int i=-1;
		while(true){
			do{
				i++;
			}while(i < max_road && iy != from[i]);
			if(i >= max_road){
				break;
			}
			
			for(int ix=1; ix<=max_money; ix++){	//コスト限界
				if(iy != from[i]){
					continue;
				}
				
				if(ix >= costd[i]){
					//移動するよ！(時間短縮できるなら。)
					table[to[i]][ix] = min(table[to[i]][ix], table[iy][ix-costd[i]] + timed[i]);
					//cout << "table[" << to[i] << "][" << ix << "] = " << table[to[i]][ix] << endl;
				}
			}
		}
		
		//結局の所...
		mind = table[iy][0];
		for(int i=1; i<=max_money; i++){
			mind = min(mind,table[iy][i]);
			table[iy][i] = mind;
		}
	}
	
	//ぜぇー...
	if(table[max_city][max_money] == 99999){
		cout << -1 << endl;
	}else{
		cout << table[max_city][max_money] << endl;
	}
	
	return 0;
}
0