結果

問題 No.134 走れ！サブロー君
ユーザー ciel
提出日時 2015-10-24 14:12:29
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 1,521 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 59,200 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-10-14 17:15:03
合計ジャッジ時間 1,040 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |         scanf("%lf%lf%d",&X,&Y,&N);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:51:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |                         scanf("%lf%lf%lf",&a[i].first,&a[i].second,&cost[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <algorithm>
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define INF 99999999
using namespace std;
typedef double Weight;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
const int M = 20;
Weight best[1<<M][M];
Weight total[1<<M][M];
Weight shortestHamiltonPath(const Matrix &dist, const Array &cost) {
    int n=cost.size();
    int N = 1 << n;
    REP(S,N) REP(i,n) best[S][i] = total[S][i]=INF;
    best[0][0] = 0;
    total[0][0] = 0;
    REP(i,n) total[0][0] += cost[i];
    REP(S,N) REP(j,n) if (!(S&(1<<j))) REP(i,n) {
        Weight time = dist[i][j]*(total[S][i]+100)/120 + cost[j];
        if (best[S|(1<<j)][j] >= best[S][i] + time) {
            best[S|(1<<j)][j] = best[S][i] + time;
            total[S|(1<<j)][j] = total[S][i] - cost[j];
        }
    }
    //int t = max_element(best[N-1], best[N-1]+n) - best[N-1];
    //path.clear(); buildPath(N-1, t, path);
    return best[N-1][0];
}
int main(){
    double X,Y;
    int N;
    scanf("%lf%lf%d",&X,&Y,&N);
    Array cost(N+1);
    Matrix dist(N+1);dist[0].resize(N+1);
    {
        vector<pair<double,double> >a(N+1);
        a[0].first=X,a[0].second=Y;
        for(int i=1;i<=N;i++){
            dist[i].resize(N+1);
            scanf("%lf%lf%lf",&a[i].first,&a[i].second,&cost[i]);
        }
        for(int i=0;i<=N;i++)for(int j=0;j<=N;j++)dist[i][j]=fabs(a[i].first-a[j].first)+fabs(a[i].second-a[j].second);
    }
    printf("%f\n",shortestHamiltonPath(dist,cost));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0