結果

問題 No.1 道のショートカット
ユーザー 158b
提出日時 2015-05-17 18:13:36
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,248 bytes
コンパイル時間 640 ms
コンパイル使用メモリ 62,676 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2024-07-08 04:00:43
合計ジャッジ時間 7,265 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

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