#include #include #include #include static const long INF=1e10; class Node { //このdijkstra法で使用するnode int x; int y; long minFromCost; long comeCost; std::vector vToNodeInduces; bool bDone; bool bInQueue; public: class Comparater { public: bool operator() (const Node* n1, const Node* n2) { return (n2->getMinFromCost() < n1->getMinFromCost()); } }; Node(int x,int y, long minFromCost, long comeCost, std::vector vToNodeInduces ) : x(x),y(y),minFromCost(minFromCost),comeCost(comeCost),vToNodeInduces(vToNodeInduces),bDone(false), bInQueue(false) { } void clear() { minFromCost=INF; bDone=false; bInQueue=false; } int getX() { return x; } int getY() { return y; } long getMinFromCost() const { return this->minFromCost; } void setMinFromCost(long minFromCost) { this->minFromCost = minFromCost; } long getComeCost() const { return this->comeCost; } void setComeCost(long comeCost) { this->comeCost = comeCost; } bool isInQueue() const { return bInQueue; } void setInQueue(bool b) { bInQueue=b; } bool isDone() const { return bDone; } void setDone(bool b) { bDone=b; } const std::vector* getToNodeInduces() const { return &vToNodeInduces; } }; typedef std::vector::const_iterator VCL_ITR; typedef std::vector::iterator VNODE_ITR; void updateCostByDijkstra(Node& firstNode, std::vector& nodeList)//, std::vector& targetNodes): { // firstNodeからのnodeList内の全ノードに対して移動するのにかかるコストを取得 // ただし、dijkstra法なので、0<=cost std::priority_queue,Node::Comparater> queue; queue.push( &firstNode ); //int count=0; //bool getTarget=false; while( !queue.empty() ) { // キューが空でない限り // キュー取り出し Node* pDoneNode=queue.top(); queue.pop(); pDoneNode->setDone(true); pDoneNode->setInQueue(false); //std::cout << count++ << std::endl; // if targetNodes: // getTarget=True // for t in targetNodes: // if not t.done: // getTarget=False // break // if getTarget: // return for( VCL_ITR itIndex=pDoneNode->getToNodeInduces()->begin(); itIndex != pDoneNode->getToNodeInduces()->end(); ++itIndex ) { if( nodeList[*itIndex].isDone() ) // 確定済みはもう良い?のだろうか? continue; // 接続先ノードを更新 long i=*itIndex; long current = pDoneNode->getMinFromCost() + nodeList[i].getComeCost(); if ( nodeList[i].getMinFromCost() == INF || current < nodeList[i].getMinFromCost() ) { nodeList[i].setMinFromCost( current ); if( nodeList[i].isInQueue() == false ) { nodeList[i].setInQueue(true); queue.push( &nodeList[i] ); // std::cout << "[" << pDoneNode->getX() << "," << pDoneNode->getY() << "]" << "->[" << nodeList[i].getX() << "," << nodeList[i].getY() << "]" << "=" << nodeList[i].getMinFromCost() << "(" << nodeList[i].getComeCost() << ")" << std::endl; } } } } } long glEdgeCount=0; long HP=0; int oasisPos[]={0,0}; long glOasisIndex = -1; int** damageOfPos = NULL; std::vector vNodes; int main() { std::cin >> glEdgeCount >> HP >> oasisPos[0] >> oasisPos[1]; if( !( oasisPos[0]==0 && oasisPos[1]==0 ) ) { glOasisIndex=oasisPos[1]-1 + (oasisPos[0]-1)*glEdgeCount; } // 二次元配列の使い方がよくわからなくなり、xy逆になってしまった・・・。 damageOfPos = new int*[glEdgeCount]; for( int y=0; y> damageOfPos[y][x]; } // for( int y=0; y vToNodeInduces; for(int i=0; i < sizeof(dx)/sizeof(int); i++ ) { int nextX = x+dx[i]; int nextY = y+dy[i]; if( ( 0<=nextX && nextX < glEdgeCount ) && ( 0<=nextY && nextY < glEdgeCount ) ) { vToNodeInduces.push_back( nextY + nextX*glEdgeCount ); } } Node node( x, y, INF, damageOfPos[y][x], vToNodeInduces ); vNodes.push_back( node ); } } // 最初の点のコストを0に初期化 vNodes[0].setMinFromCost(0); updateCostByDijkstra(vNodes[0],vNodes); // for( VNODE_ITR itr=vNodes.begin(); itr != vNodes.end(); ++itr ) // std::cout << "[" << itr->getX() << "," << itr->getY() << "]=" << itr->getMinFromCost() << std::endl; if( vNodes.back().getMinFromCost() < HP ) { std::cout << "YES" << std::endl; } else { // HPが足りなかった //std::cout << "HP" << HP << "not enouph.cost" << vNodes.back().getMinFromCost() << std::endl; // オアシス経由でいけるか試す if( glOasisIndex==-1 ) { // オアシスがない // 死亡 // print('not exist oasis') std::cout << "NO" << std::endl; } else { if( vNodes[glOasisIndex].getMinFromCost() < HP ) { // オアシスまではいける // HPをオアシスについた状態から2倍に HP = (HP-vNodes[glOasisIndex].getMinFromCost())*2; // HPが足りなかった //std::cout << "oasis exists [toCost]=" << vNodes[glOasisIndex].getMinFromCost() << std::endl; //std::cout << "HP recovery to " << HP << std::endl; // 最初の点をoasisにしてもう一度dijkstra for( VNODE_ITR itNode = vNodes.begin(); itNode != vNodes.end(); ++itNode ) { itNode->clear(); } vNodes[glOasisIndex].setMinFromCost(0); updateCostByDijkstra(vNodes[glOasisIndex],vNodes); // for node in nodes: // print( "[" + str(node.x) + "," + str(node.y) + "]="+str(node.minFromCost) ) if( vNodes.back().getMinFromCost() < HP ) std::cout << "YES" << std::endl; else std::cout << "NO" << std::endl; } else { // オアシスはあるけど、オアシスにも辿り着けない // アウト // print('cant reach oasis{} HP{}'.format( nodes[oasisIndex].minFromCost, HP)) std::cout << "NO" << std::endl; } } } // メモリ解放 // vectorで良かったのでは・・・ for( int x=0; x