結果

問題 No.1 道のショートカット
コンテスト
ユーザー FF256grhy
提出日時 2015-05-02 15:20:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,859 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 25,088 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 03:55:46
合計ジャッジ時間 1,262 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:24:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |         scanf("%d%d%d", &n, &cash, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:25:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |         for(i = 0; i < v; i++) { scanf("%d", &s[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:26:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |         for(i = 0; i < v; i++) { scanf("%d", &g[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:27:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   27 |         for(i = 0; i < v; i++) { scanf("%d", &m[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~
main.cpp:28:39: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |         for(i = 0; i < v; i++) { scanf("%d", &t[i]); }
      |                                  ~~~~~^~~~~~~~~~~~~

ソースコード

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