結果
問題 | No.134 走れ!サブロー君 |
ユーザー |
![]() |
提出日時 | 2020-08-18 15:45:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 5,147 bytes |
コンパイル時間 | 7,237 ms |
コンパイル使用メモリ | 224,840 KB |
最終ジャッジ日時 | 2025-01-13 03:09:09 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#pragma GCC optimize ("Ofast")#pragma GCC target ("avx2")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>using namespace std;inline int my_getchar_unlocked(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread_unlocked(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar_unlocked();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}inline void rd(double &x){int k;int m=0;int p=0;double r = 1;x = 0;for(;;){k = my_getchar_unlocked();if(k=='-'){m = 1;break;}if(k=='.'){p = 1;break;}if('0'<=k&&k<='9'){x = k - '0';break;}}for(;;){k = my_getchar_unlocked();if(k=='.'){p = 1;continue;}if(k<'0'||k>'9'){break;}if(p){r *= 0.1;x += r * (k - '0');}else{x = x * 10 + k - '0';}}if(m){x = -x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite_unlocked(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar_unlocked(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar_unlocked(a);}int WRITER_DOUBLE_DIGIT = 15;inline int writerDigit_double(){return WRITER_DOUBLE_DIGIT;}inline void writerDigit_double(int d){WRITER_DOUBLE_DIGIT = d;}inline void wt_L(double x){const int d = WRITER_DOUBLE_DIGIT;int k;int r;double v;if(x!=x || (x==x+1 && x==2*x)){my_putchar_unlocked('E');my_putchar_unlocked('r');my_putchar_unlocked('r');return;}if(x < 0){my_putchar_unlocked('-');x = -x;}x += 0.5 * pow(0.1, d);r = 0;v = 1;while(x >= 10*v){v *= 10;r++;}while(r >= 0){r--;k = floor(x / v);if(k >= 10){k = 9;}if(k <= -1){k = 0;}x -= k * v;v *= 0.1;my_putchar_unlocked(k + '0');}if(d > 0){my_putchar_unlocked('.');v = 1;for(r=(0);r<(d);r++){v *= 0.1;k = floor(x / v);if(k >= 10){k = 9;}if(k <= -1){k = 0;}x -= k * v;my_putchar_unlocked(k + '0');}}}int n;int m;int x[14];int y[14];int p;int q;double w[13];double dp[1 << 13][13];double dist(int i, int j){return abs(x[i] - x[j]) + abs(y[i] - y[j]);}template <class T> void chmin(T& x, const T& v){if (x > v){x = v;}}int main(){int i, s, v;rd(p);rd(q);rd(n);{int Nzj9Y0kE;for(Nzj9Y0kE=(0);Nzj9Y0kE<(n);Nzj9Y0kE++){rd(x[Nzj9Y0kE]);rd(y[Nzj9Y0kE]);rd(w[Nzj9Y0kE]);}}m = 1 << n;x[n] = p;y[n] = q;int QAAnbtfa;double om7Ebh6q;if(n==0){om7Ebh6q = 0;}else{om7Ebh6q = w[0];for(QAAnbtfa=(1);QAAnbtfa<(n);QAAnbtfa++){om7Ebh6q += w[QAAnbtfa];}}double w_sum = om7Ebh6q;double k = (w_sum + 100) / 120;for(i=(0);i<(m);i++){int j;for(j=(0);j<(n);j++){dp[i][j] = 4611686016279904256LL;}}for(i=(0);i<(n);i++){dp[1 << i][i] = dist(i, n) * k + w[i];}for(s=(0);s<(m);s++){int v;k = 0;for(v=(0);v<(n);v++){if (!(s & 1 << v)){k += w[v];}}k = (k + 100) / 120;for(v=(0);v<(n);v++){if (s & 1 << v){int u;for(u=(0);u<(n);u++){if (!(s & 1 << u)){chmin(dp[s | 1 << u][u], dp[s][v] + dist(v, u) * k + w[u]);}}}}}double ans = 4611686016279904256LL;k = 5.0 / 6.0;for(v=(0);v<(n);v++){chmin(ans, dp[m - 1][v] + k * dist(v, n));}wt_L(ans);wt_L('\n');return 0;}// cLay varsion 20200509-1// --- original code ---// int n, m, x[14], y[14], p, q;// double w[13], dp[1 << 13][13];// double dist(int i, int j) {// return abs(x[i] - x[j]) + abs(y[i] - y[j]);// }// template <class T> void chmin(T& x, const T& v) {// if (x > v) x = v;// }// {// rd(p, q, n, (x, y, w)(n));// m = 1 << n;// x[n] = p;// y[n] = q;// double w_sum = sum(w(n)), k = (w_sum + 100) / 120;// rep(i, m) rep(j, n) dp[i][j] = ll_inf;// rep(i, n) dp[1 << i][i] = dist(i, n) * k + w[i];// rep(s, m) {// k = 0;// rep(v, n) if (!(s & 1 << v)) k += w[v];// k = (k + 100) / 120;// rep(v, n) if (s & 1 << v) {// rep(u, n) if (!(s & 1 << u)) {// chmin(dp[s | 1 << u][u], dp[s][v] + dist(v, u) * k + w[u]);// }// }// }//// double ans = ll_inf;// k = 5.0 / 6.0;// rep(v, n) chmin(ans, dp[m - 1][v] + k * dist(v, n));// wt(ans);// }