結果

問題 No.134 走れ！サブロー君
ユーザー masa
提出日時 2015-10-09 13:17:37
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0