#line 1 "..\\Main.cpp" #include #include #include #include #include #line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" #include #include #line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\csr-array.hpp" 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 #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector>; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool 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, bool 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; } 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]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(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 #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\dijkstra.hpp" #include namespace nachia{ // require : // Weight + Weight // Weight < Weight // constructor Weight(Weight2) template struct DijkstraShortestPath { private: nachia::Graph g; std::vector dist; std::vector pre; std::vector ord; public: DijkstraShortestPath( nachia::Graph graph, const std::vector& weight, const std::vector>& starting, const Weight Inf, int goal = -1 ){ using T = std::pair; g = std::move(graph); auto adj = g.getEdgeIndexArray(); std::vector D(g.numVertices(), Inf); std::vector E(g.numVertices(), -1); struct Comp { bool operator()(T a, T b) const noexcept { return b < a; }; }; std::priority_queue, Comp> Q; ord.clear(); for(auto a : starting) if(a.second < D[a.first]){ D[a.first] = a.second; Q.push({ a.second, a.first }); } while(Q.size()){ int p = Q.top().second; Weight d = Q.top().first; Q.pop(); if(D[p] < d) continue; ord.push_back(p); if(p == goal) break; for(auto e : adj[p]){ int q = g[e].from ^ g[e].to ^ p; Weight nxd = d + Weight(weight[e]); if(!(nxd < D[q])) continue; E[q] = e; D[q] = nxd; Q.emplace(nxd, q); } } dist = std::move(D); pre = std::move(E); } Weight distTo(int v) const noexcept { return dist[v]; } int prevEdge(int v) const noexcept { return pre[v]; } int prevVertex(int v) const noexcept { return pre[v] >= 0 ? g[pre[v]].from ^ g[pre[v]].to ^ v : -1; } std::vector pathTo(int v) const { std::vector res; while(pre[v] >= 0){ res.push_back(pre[v]); v = prevVertex(v); } std::reverse(res.begin(), res.end()); return res; } std::vector getSearchOrder() const { return ord; } Graph getTree() const { Graph res(g.numVertices(), false); for(int i=0; i= 0){ res.addEdge(prevVertex(i), i); } return res; } }; } // namespace nachia #line 8 "..\\Main.cpp" using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int N, M, K, T; cin >> N >> M >> K >> T; int Q = (N-1) + (M-1); if(T >= Q){ cout << "0\n"; return 0; } auto idx = [&](int n, int m, int t){ return t * N * M + n * M + m; }; vector> C(N, vector(M)); auto D = C; rep(k,K){ int a,b,c,d; cin >> a >> b >> c >> d; a--; b--; if(c >= Q) c = Q; C[a][b] = c; D[a][b] = d; } auto g = nachia::Graph(N*M*Q*2, false); vector W; rep(n,N) rep(m,M) rep(t,Q*2){ if(n != 0 && t != Q*2-1){ g.addEdge(idx(n,m,t), idx(n-1,m,t+1)); W.push_back(0); g.addEdge(idx(n-1,m,t), idx(n,m,t+1)); W.push_back(0); } if(m != 0 && t != Q*2-1){ g.addEdge(idx(n,m,t), idx(n,m-1,t+1)); W.push_back(0); g.addEdge(idx(n,m-1,t), idx(n,m,t+1)); W.push_back(0); } if(t != Q*2-1){ g.addEdge(idx(n,m,t), idx(n,m,t+1)); W.push_back(0); } if(C[n][m] >= 2){ g.addEdge(idx(n,m,t), idx(n,m,max(t-C[n][m]+1,0))); W.push_back(D[n][m]); } } auto dist = nachia::DijkstraShortestPath(g, W, {{idx(0,0,Q),0}}, INF); i64 ans = dist.distTo(idx(N-1,M-1,Q*2-1)); if(ans == INF) ans = -1; cout << ans << endl; return 0; }