#include #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ 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 int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, std::vector> edges, bool rev){ mn = n; std::vector 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>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i 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::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 E; std::vector I; public: AdjacencyListEdgeIndexed(int n, const std::vector>& edges, bool rev){ mn = n; std::vector 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 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 #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]; nachia::AdjacencyList E; double D[maxV][NV]; int main(){ cin >> X >> Y; X--; Y--; cin >> N; { vector> 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> 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>> 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 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