結果
問題 | No.1599 Hikyaku |
ユーザー | 👑 Nachia |
提出日時 | 2022-01-31 00:28:37 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,169 ms / 7,500 ms |
コード長 | 6,563 bytes |
コンパイル時間 | 1,579 ms |
コンパイル使用メモリ | 97,264 KB |
実行使用メモリ | 59,924 KB |
最終ジャッジ日時 | 2023-09-02 01:56:31 |
合計ジャッジ時間 | 37,216 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 147 ms
52,900 KB |
testcase_01 | AC | 183 ms
53,864 KB |
testcase_02 | AC | 191 ms
53,956 KB |
testcase_03 | AC | 158 ms
57,124 KB |
testcase_04 | AC | 1,062 ms
50,316 KB |
testcase_05 | AC | 361 ms
50,272 KB |
testcase_06 | AC | 940 ms
50,324 KB |
testcase_07 | AC | 377 ms
50,328 KB |
testcase_08 | AC | 1,096 ms
50,552 KB |
testcase_09 | AC | 273 ms
49,676 KB |
testcase_10 | AC | 340 ms
49,596 KB |
testcase_11 | AC | 217 ms
49,616 KB |
testcase_12 | AC | 323 ms
58,676 KB |
testcase_13 | AC | 252 ms
54,428 KB |
testcase_14 | AC | 120 ms
54,436 KB |
testcase_15 | AC | 156 ms
52,848 KB |
testcase_16 | AC | 414 ms
55,760 KB |
testcase_17 | AC | 1,074 ms
50,312 KB |
testcase_18 | AC | 1,052 ms
50,316 KB |
testcase_19 | AC | 1,133 ms
52,128 KB |
testcase_20 | AC | 1,169 ms
52,152 KB |
testcase_21 | AC | 1,127 ms
51,484 KB |
testcase_22 | AC | 1,150 ms
51,368 KB |
testcase_23 | AC | 1,085 ms
51,356 KB |
testcase_24 | AC | 1,111 ms
51,364 KB |
testcase_25 | AC | 1,120 ms
52,728 KB |
testcase_26 | AC | 946 ms
59,924 KB |
testcase_27 | AC | 615 ms
57,164 KB |
testcase_28 | AC | 609 ms
57,088 KB |
testcase_29 | AC | 445 ms
55,756 KB |
testcase_30 | AC | 266 ms
54,420 KB |
testcase_31 | AC | 149 ms
52,900 KB |
testcase_32 | AC | 146 ms
52,796 KB |
testcase_33 | AC | 155 ms
52,868 KB |
testcase_34 | AC | 567 ms
57,128 KB |
testcase_35 | AC | 825 ms
58,596 KB |
testcase_36 | AC | 1,118 ms
50,292 KB |
testcase_37 | AC | 1,047 ms
50,244 KB |
testcase_38 | AC | 1,073 ms
50,396 KB |
testcase_39 | AC | 1,038 ms
50,552 KB |
testcase_40 | AC | 1,103 ms
51,092 KB |
testcase_41 | AC | 102 ms
52,868 KB |
testcase_42 | AC | 151 ms
52,852 KB |
testcase_43 | AC | 100 ms
52,936 KB |
testcase_44 | AC | 430 ms
55,688 KB |
testcase_45 | AC | 430 ms
55,800 KB |
testcase_46 | AC | 552 ms
57,020 KB |
testcase_47 | AC | 552 ms
57,064 KB |
testcase_48 | AC | 1,040 ms
49,476 KB |
testcase_49 | AC | 149 ms
53,128 KB |
testcase_50 | AC | 280 ms
54,668 KB |
testcase_51 | AC | 423 ms
55,864 KB |
testcase_52 | AC | 330 ms
50,492 KB |
ソースコード
#include <vector> #include <utility> namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector<int>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector<int> E; std::vector<int> I; public: AdjacencyList(int n, std::vector<std::pair<int,int>> edges, bool rev){ mn = n; std::vector<int> buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector<std::vector<int>>& edges = {}){ int n = mn = edges.size(); std::vector<int> buf(n+1, 0); for(int i=0; i<n; i++) buf[i+1] = buf[i] + edges[i].size(); E.resize(buf[n]); for(int i=0; i<n; i++) for(int j=0; j<(int)edges[i].size(); j++) E[buf[i]+j] = edges[i][j]; I = std::move(buf); } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector<int> buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u<n; u++) for(int v : operator[](u)) res.E[--buf[v]] = u; res.I = std::move(buf); return res; } }; struct AdjacencyListEdgeIndexed{ public: struct Edge { int to; int edgeidx; }; struct AdjacencyListRange{ using iterator = typename std::vector<Edge>::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Edge& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector<Edge> E; std::vector<int> I; public: AdjacencyListEdgeIndexed(int n, const std::vector<std::pair<int,int>>& edges, bool rev){ mn = n; std::vector<int> buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = { v, i }; if(rev) E[--buf[v]] = { u, i }; } I = std::move(buf); } AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {} AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int num_edges() const { return E.size(); } AdjacencyListEdgeIndexed reversed_edges() const { AdjacencyListEdgeIndexed res; int n = res.mn = mn; std::vector<int> buf(n+1, 0); for(auto [v,i] : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u<n; u++) for(auto [v,i] : operator[](u)) res.E[--buf[v]] = {u,i}; res.I = std::move(buf); return res; } }; } // namespace nachia #include <iostream> #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]; nachia::AdjacencyList E; double D[maxV][NV]; int main(){ cin >> X >> Y; X--; Y--; cin >> N; { vector<pair<int,int>> edges; rep(y,H) rep(x,W-1) edges.push_back({ pos2id(y,x), pos2id(y,x+1) }); rep(y,H-1) rep(x,W) edges.push_back({ pos2id(y,x), pos2id(y+1,x) }); E = nachia::AdjacencyList(NV, edges, true); } 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]); 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;