結果

問題 No.1599 Hikyaku
ユーザー 👑 NachiaNachia
提出日時 2021-07-10 15:20:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,874 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 91,432 KB
実行使用メモリ 65,592 KB
最終ジャッジ日時 2024-07-02 02:31:56
合計ジャッジ時間 42,058 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 224 ms
62,872 KB
testcase_01 AC 267 ms
63,408 KB
testcase_02 AC 260 ms
63,276 KB
testcase_03 AC 268 ms
62,744 KB
testcase_04 AC 1,136 ms
65,076 KB
testcase_05 AC 533 ms
63,448 KB
testcase_06 AC 1,187 ms
65,336 KB
testcase_07 AC 606 ms
65,108 KB
testcase_08 AC 1,259 ms
65,340 KB
testcase_09 AC 498 ms
62,964 KB
testcase_10 AC 553 ms
62,896 KB
testcase_11 AC 435 ms
62,880 KB
testcase_12 AC 504 ms
64,276 KB
testcase_13 AC 383 ms
64,536 KB
testcase_14 AC 202 ms
62,876 KB
testcase_15 AC 234 ms
62,740 KB
testcase_16 AC 553 ms
62,872 KB
testcase_17 WA -
testcase_18 AC 1,122 ms
63,536 KB
testcase_19 AC 1,324 ms
65,196 KB
testcase_20 AC 1,286 ms
65,332 KB
testcase_21 AC 1,298 ms
64,776 KB
testcase_22 AC 1,275 ms
64,876 KB
testcase_23 AC 1,284 ms
64,684 KB
testcase_24 AC 1,251 ms
64,680 KB
testcase_25 AC 1,305 ms
65,592 KB
testcase_26 AC 1,160 ms
64,156 KB
testcase_27 AC 801 ms
64,280 KB
testcase_28 AC 803 ms
63,516 KB
testcase_29 AC 577 ms
63,636 KB
testcase_30 AC 376 ms
62,872 KB
testcase_31 AC 221 ms
63,000 KB
testcase_32 AC 225 ms
62,876 KB
testcase_33 AC 228 ms
62,876 KB
testcase_34 AC 744 ms
62,868 KB
testcase_35 AC 956 ms
63,384 KB
testcase_36 AC 1,253 ms
63,644 KB
testcase_37 AC 1,171 ms
63,528 KB
testcase_38 AC 1,191 ms
63,432 KB
testcase_39 AC 1,182 ms
63,704 KB
testcase_40 AC 1,274 ms
64,304 KB
testcase_41 AC 159 ms
62,872 KB
testcase_42 AC 225 ms
62,900 KB
testcase_43 AC 160 ms
63,000 KB
testcase_44 WA -
testcase_45 AC 555 ms
62,876 KB
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 AC 224 ms
63,004 KB
testcase_50 AC 392 ms
62,868 KB
testcase_51 AC 559 ms
62,868 KB
testcase_52 AC 543 ms
63,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<class T>
using nega_queue = priority_queue<T,vector<T>,greater<T>>;

const int INF = 1001001001;

const int W = 600;
const int H = 600;
const int NV = W * H; // number of vertices
const int maxV = 7;

struct Start{ int id,v; };

int pos2id(int y,int x){ return y * W + x; }

int X,Y;
int N;
vector<Start> hikyaku;
double dt[maxV];
double V[maxV];
double T[maxV][NV];
vector<int> E[NV];

double D[maxV][NV];

int main(){
  cin >> X >> Y; X--; Y--;
  cin >> N;

  rep(y,H) rep(x,W-1) E[pos2id(y,x)].push_back(pos2id(y,x+1));
  rep(y,H) rep(x,W-1) E[pos2id(y,x+1)].push_back(pos2id(y,x));
  rep(y,H-1) rep(x,W) E[pos2id(y,x)].push_back(pos2id(y+1,x));
  rep(y,H-1) rep(x,W) E[pos2id(y+1,x)].push_back(pos2id(y,x));

  hikyaku.resize(N);
  rep(i,N){
    int x,y,v; cin >> x >> y >> v;
    x--; y--; v--;
    hikyaku[i] = { pos2id(y,x),v };
  }

  rep(v,maxV) V[v] = 1+v;
  rep(v,maxV) dt[v] = 1000.0 / (1+v);
  
  rep(v,maxV) rep(i,NV) T[v][i] = INF;

  {
    vector<vector<int>> I(maxV);
    for(auto a : hikyaku){
      I[a.v].push_back(a.id);
      T[a.v][a.id] = 0;
    }
    rep(v,maxV){
      rep(i,I[v].size()){
        int p = I[v][i];
        for(int e : E[p]) if(T[v][e] >= INF - 1.0){
          T[v][e] = T[v][p] + dt[v];
          I[v].push_back(e);
        }
      }
    }
  }
  
  rep(v,maxV) rep(i,NV) D[v][i] = INF;

  nega_queue<pair<double,pair<int,int>>> Q;
  D[hikyaku[0].v][hikyaku[0].id] = 0.0;
  Q.push(make_pair(0.0,make_pair(hikyaku[0].v,hikyaku[0].id)));

  while(Q.size()){
    double d = Q.top().first;
    int v = Q.top().second.first;
    int p = Q.top().second.second;
    Q.pop();
    if(D[v][p] != d) continue;
    for(int nxv=v+1; nxv<maxV; nxv++) if(D[nxv][p] > max(T[nxv][p],d)){
      D[nxv][p] = max(T[nxv][p],d);
      Q.push(make_pair(D[nxv][p],make_pair(nxv,p)));
    }
    for(int e : E[p]){
      if(D[v][e] > D[v][p] + dt[v]){
        D[v][e] = D[v][p] + dt[v];
        Q.push(make_pair(D[v][e],make_pair(v,e)));
      }
      for(int nxv=v+1; nxv<maxV; nxv++){
        double nxd = d + dt[v];
        if(d < T[nxv][p] && T[nxv][e] <= d + dt[v]){
          double t0 = T[nxv][e] - D[v][p];
          double t = (1000.0+V[nxv]*t0) / (V[v]+V[nxv]);
          double cand = d + t * 2 - t0;
          nxd = min(nxd,max(d+dt[nxv],cand));
          if(D[nxv][e] <= nxd) continue;
          D[nxv][e] = nxd;
          Q.push(make_pair(nxd,make_pair(nxv,e)));
        }
      }
    }
  }

  double ans = INF;
  rep(v,maxV) ans = min(ans,D[v][pos2id(Y,X)]);
  cout.precision(10); cout << fixed;
  cout << ans << endl;
  return 0;
}

struct ios_do_not_sync{
  ios_do_not_sync(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} ios_do_not_sync_inst;
0