結果

問題 No.1599 Hikyaku
ユーザー 👑 Nachia
提出日時 2021-07-10 16:09:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,276 ms / 7,500 ms
コード長 2,959 bytes
コンパイル時間 1,277 ms
コンパイル使用メモリ 88,632 KB
最終ジャッジ日時 2025-01-23 00:21:34
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

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 + dt[v]){
D[v][e] = d + dt[v];
Q.push(make_pair(D[v][e],make_pair(v,e)));
}
double nxd = dt[v];
int pv = v;
for(int nxv=v+1; nxv<maxV; nxv++){
double t0 = d + nxd - max(d - dt[nxv], T[nxv][e]);
//cout << "p = " << p << ", e = " << e << ", pv = " << pv << ", nxv = " << nxv << ", t0 = " << t0 << endl;
if(t0 < 0) continue;
t0 = min(t0,dt[pv]+dt[nxv]);
double t = nxd - t0 * (V[nxv] - V[pv]) / (V[nxv] + V[pv]);
nxd = t; pv = nxv;
if(D[nxv][e] <= d+nxd) continue;
D[nxv][e] = d+nxd;
Q.push(make_pair(d+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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0