#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class GoSabrou { public: void solve(void) { // 巡回セールスマン問題の応用 int x0,y0; cin>>x0>>y0; int N; cin>>N; // 配達先 vector> dest; // 出発地も登録しておく dest.emplace_back(x0,y0,0); REP(i,N) { int x,y; double w; cin>>x>>y>>w; dest.emplace_back(x,y,w); } ++N; // 距離を事前計算しておく const int inf = (1<<30); vector> dist(N,vector(N,inf)); REP(i,N) FOR(j,i+1,N) { const auto &p = dest[i]; const auto &q = dest[j]; // 距離はマンハッタン距離 int d = abs(get<0>(p)-get<0>(q)) + abs(get<1>(p)-get<1>(q)); dist[i][j] = dist[j][i] = d; } // 総荷重量を計算しておく // weights[unvis] := 未配達先が unvis であるときの総重量 vector weights(1<(dest[i]); weights[unvis] = w; } // dp[unvis][i] := 未配達先が unvis で現在地が v のときの配達終了までの最短時間 vector> dp(1<(N,inf)); // O((1<= 0; --unvis) { // 次の移動先 v 毎 REP(v,N) { // 移動前 u 毎 REP(u,N) { // 移動前が未到達なら飛ばす if ( unvis & (1<(dest[v]); dp[unvis][v] = min(dp[unvis][v], dp[unvis|(1<solve(); delete obj; return 0; } #endif