結果

問題 No.134 走れ！サブロー君
ユーザー masamasa
提出日時 2015-10-09 13:17:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,918 bytes
コンパイル時間 719 ms
コンパイル使用メモリ 73,252 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-10-14 17:15:02
合計ジャッジ時間 1,353 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 5 ms
5,248 KB
testcase_08 AC 9 ms
5,760 KB
testcase_09 AC 9 ms
5,888 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 1 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:81:87: warning: ‘next_stat’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |                 ans = min(ans, dp[n_stat - 1][i] + calc_cost120(i, 0, weight[next_stat]));
      |                                                                                       ^

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <sstream>

using namespace std;

const double INF = 1e8;

vector<int> x, y;
vector<double> w;

string binstr(int n) {
	stringstream ss;
	ss << static_cast<bitset<6> >(n);

	return ss.str();
}

double calc_cost120(int from, int to, double weight_now) {
	return w[to] * 120 + (weight_now + 100) * (abs(x[to] - x[from]) + abs(y[to] - y[from]));
}

int main() {

	int n;
	x.assign(20, 0), y.assign(20, 0), w.assign(20, 0);
	cin >> x[0] >> y[0] >> n;

	double total_w = 0;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i] >> w[i];
		total_w += w[i];
	}
	x[n+1] = x[0];
	y[n+1] = y[0];

	int n_stat = (1 << (n + 1));
	vector<double> weight(n_stat + 1, -1);
	weight[1] = total_w;

	vector< vector<double> > dp(n_stat, vector<double>(n + 1, INF));

	int next_stat;

	dp[1][0] = 0;
	for (int stat = 1; stat < n_stat; stat++) {
		for (int from = 0; from <= n; from++) {
			if (dp[stat][from] == INF) {
				continue;
			}

			for (int to = 1; to <= n; to++) {
				next_stat = stat | (1 << to);
				if (stat == next_stat) {
					continue;
				}

				if (weight[next_stat] == -1) {
					weight[next_stat] = weight[stat] - w[to];
				}
/*
printf("stat %s -> %s:  %d -> %d: w %f -> %f: dp_from %f + calc %f = %f : dp_next %f -> ",
	binstr(stat).c_str(), binstr(next_stat).c_str(), from, to, weight[stat], weight[next_stat],
	dp[stat][from], calc_cost120(from, to, weight[stat]),
	dp[stat][from] + calc_cost120(from, to, weight[stat]),
	dp[next_stat][to]);
*/
				dp[next_stat][to] = min(dp[next_stat][to], dp[stat][from] + calc_cost120(from, to, weight[stat]));

// printf("dp_next_a %f\n", dp[next_stat][to]);
			}
		}
	}

	double ans = INF;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, dp[n_stat - 1][i] + calc_cost120(i, 0, weight[next_stat]));
	}

	printf("%.12f\n", 1.0 * ans / 120);
	return 0;
}
0