#include #include #include #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::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 Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } int xorval() const { return from ^ to; } }; Graph() : m_n(0), m_e(0), m_isUndir(false) {} explicit Graph(int n, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} explicit Graph(int n, const std::vector>& edges, int undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, int offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } template static std::pair> InputWeighted(Cin& cin, int n, bool undirected, int m, int offset = 0){ Graph res(n, undirected, m); std::vector wt(m); for(int i=0; i> u >> v >> wt[i]; res[i].from = u - offset; res[i].to = v - offset; } return std::make_pair(std::move(res), std::move(wt)); } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia #include #include using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) template using nega_queue = priority_queue,greater>; 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 hikyaku; double dt[maxV]; double V[maxV]; double T[maxV][NV]; double D[maxV][NV]; int main(){ cin >> X >> Y; X--; Y--; cin >> N; auto graph = nachia::Graph(H*W, true); rep(y,H) rep(x,W-1) graph.addEdge(pos2id(y,x), pos2id(y,x+1)); rep(y,H-1) rep(x,W) graph.addEdge(pos2id(y,x), pos2id(y+1,x)); auto E = graph.getAdjacencyArray(); 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] = 1.0 / (1+v); rep(v,maxV) rep(i,NV) T[v][i] = 1.0e100; { vector> 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] >= 1.0e50){ T[v][e] = T[v][p] + dt[v]; I[v].push_back(e); } } } } rep(v,maxV) rep(i,NV) D[v][i] = 1.0e100; nega_queue>> Q; D[hikyaku[0].v][hikyaku[0].id] = 0.0; Q.push(make_pair(0.0,make_pair(hikyaku[0].v,hikyaku[0].id))); auto see = [&](double nxd, int nxv, int p) { if(D[nxv][p] > nxd){ D[nxv][p] = nxd; Q.push(make_pair(D[nxv][p],make_pair(nxv,p))); } }; 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 buf(maxV, 1.0e100); buf[v] = d + dt[v]; for(int nxv=v+1; nxv 1.0 || 0.0 > pt) continue; buf[nxv] = min(buf[nxv], T[nxv][e] + pt / (V[w] + V[nxv]) * 2); } if(buf[nxv] < 1.0e50) see(buf[nxv], nxv, e); } } } double ans = INF; rep(v,maxV) ans = min(ans,D[v][pos2id(Y,X)]); cout.precision(10); cout << fixed; ans *= 1000.0; 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;