結果

問題 No.1 道のショートカット
ユーザー FF256grhyFF256grhy
提出日時 2015-05-02 15:20:49
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,859 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 28,016 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-22 12:09:07
合計ジャッジ時間 1,750 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>

#define MAX_TOWN    50
#define MAX_MONEY  300
#define MAX_ROAD  1500
#define MAX_TIME  1000

int    add(int, int, int);
void marge(int, int, int);
int answer();
void print(); // デバッグ用

int n, cash, v; // N, C, V
int s[MAX_ROAD], g[MAX_ROAD], m[MAX_ROAD], t[MAX_ROAD]; // S, T, Y, M

typedef struct { int money; int time; int next;	} road;

int table[MAX_TOWN - 1][MAX_TOWN];
road list[ MAX_TOWN * (MAX_TOWN - 1) / 2 * (MAX_MONEY + 2) + 1 ];
int ptr;

int main(void) {
	int i, j, k;
	scanf("%d%d%d", &n, &cash, &v);
	for(i = 0; i < v; i++) { scanf("%d", &s[i]); }
	for(i = 0; i < v; i++) { scanf("%d", &g[i]); }
	for(i = 0; i < v; i++) { scanf("%d", &m[i]); }
	for(i = 0; i < v; i++) { scanf("%d", &t[i]); }
	
	//末尾用のダミー
	ptr = 0;
	list[ptr].money = cash + 1;
	list[ptr].time  = -1; // 解無しの時はanswerでこれがでる
	list[ptr].next  =  0;
	ptr++;
	for(i = 0;     i < n - 1; i++) {
	for(j = i + 1; j < n;     j++) {
		//先頭用のダミー
		list[ptr].money = -1;
		list[ptr].time  = MAX_TIME * MAX_ROAD + 1; // 必要ない気がする
		list[ptr].next  =  0;
		table[i][j] = ptr;
		ptr++;
	}
	}
	
	for(i = 0; i < v; i++) {
		add(table[ s[i] - 1 ][ g[i] - 1 ], m[i], t[i]); // 町番号は0オリジンにする
	}
	
	for(i = 2; i     < n; i++) { //始点と終点の差
	for(j = 0; j + i < n; j++) { //始点位置          //前回のはここが思いっきり間違ってた……
	for(k = 1; k     < i; k++) { //始点と分割点の差
		marge(i, j, k);
	}
	}
	}
	
	printf("%d\n", answer() );
	
	return 0;
}

int min(int a, int b) {
	return a < b ? a : b;
}

int add(int p, int m, int t) { // margeするときのために、終了時の探索位置を返す
	if(m > cash) { return p; }
	while(1) {
		if(m == list[p].money) {
			//change
			list[p].time = min(t, list[p].time);
			return p;
		} else if(m > list[p].money) {
			if(t > list[p].time) { return p; }
			if(list[p].next != 0) {
				//next
				p = list[p].next;
				continue;
			} else {
				//write
				list[ptr].money = m;
				list[ptr].time  = t;
				list[ptr].next  = 0;
				list[p].next = ptr;
				ptr++;
				return p;
			}
		} else { // (m < list[p].money)
			if(t > list[p].time) {
				//insert
				list[ptr].money = list[p].money;
				list[ptr].time  = list[p].time;
				list[ptr].next  = list[p].next;
				list[p].money = m;
				list[p].time  = t;
				list[p].next  = ptr;
				ptr++;
				return p;
			} else { // (t <= list[p].time)
				//delete and write
				int del = p;
				while(t <= list[del].time) {
					del = list[del].next;
				}
				list[p].money = m;
				list[p].time  = t;
				list[p].next  = del;
				return p;
			}
		}
	} // end while
}

void marge(int i, int j, int k) {
	// [j][j+i] <-- [j][j+k] + [j+k][j+i]
	
	int p = table[j]       [j + i];
	int q = table[j][j + k]       ;
	int r = table   [j + k][j + i];
	
	while(r != 0) {
		p = table[j]       [j + i];
		q = table[j][j + k]       ;
		r = list[r].next; // 先頭はダミーなので初手前進
		if(list[r].money > cash) { break; }
		while(q != 0) {
			q = list[q].next;
			if(list[q].money > cash) { break; }
			int m = list[q].money + list[r].money;
			int t = list[q].time  + list[r].time ;
			if(m <= cash) {
				p = add(p, m, t); // 投げたときに p!=0 なら、返りも p!=0 (のはず)
			} else {
				break; // 内側のループを抜ける
			}
		}
	}
}

int answer() {
	int p = list[ table[0][n - 1] ].next; // 先頭避け
	while(list[p].next != 0) {
		p = list[p].next;
	}
	return list[p].time;
}

void print() {
	printf("\n\n");
	int i, j;
	for(i = 0; i < n - 1; i++) { printf("%2d | ", i);
	for(j = 0; j < n;     j++) {
		printf("%4d ", table[i][j]);
	} printf("\n");
	}
	printf("\nlist: (ptr = %d)\n", ptr);
	for(i = 0; i < ptr; i++) {
		printf("%3d [m: %3d, t: %7d, n: %3d]\n", i, list[i].money, list[i].time, list[i].next);
	}
}
0