結果
問題 | No.1599 Hikyaku |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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 verticesconst 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;