AOJ 0234 Aizu Buried Treasureをpriority_queueを使う
ダイクストラ法で解いたのですが、サンプルは通るもWAで原因が分からず困っています。
他の方の解答と見比べてみたり、複雑になっていたところを書き換えてみたりしたのですが、
それでもACにならず、困り果てて質問している次第です。
反例でも解法自体の間違いでもいいので、わかりましたらコメント頂ければ幸いです。
宜しくお願い致します。
私の書いたコードは下記の通りです。
Stateをd(コスト),o(酸素),y,x(現在位置),l,r(同じy座標で行った範囲)として
priority_queueでdが小さいものからでてくるように<を定義しダイクストラ法を行いました。
lang
1#include <iostream> 2#include <stdio.h> 3#include <sstream> 4#include <string> 5#include <vector> 6#include <map> 7#include <queue> 8#include <algorithm> 9#include <set> 10#include <math.h> 11#include <utility> 12#include <stack> 13#include <string.h> 14#include <complex> 15using namespace std; 16 17const int INF = 1<<29; 18const double EPS = 1e-8; 19typedef vector<int> vec; 20typedef pair<int,int> P; 21struct edge{int to,cost;}; 22 23struct State{ 24 int d,o,y,x,l,r; 25 bool operator<(const State& right) const{ 26 return d == right.d ? o < right.o : d > right.d; 27 } 28}; 29 30const int dx[] = {-1,1,0}; 31const int dy[] = {0,0,1}; 32int field[10][10]; 33int d[51][10][10][10][10]; 34 35int main(){ 36 while(1){ 37 int W,H; 38 scanf("%d%d",&W,&H); 39 if(!W)break; 40 41 int f,m,o; 42 scanf("%d%d%d",&f,&m,&o); 43 for(int i=0;i<H;i++){ 44 for(int j=0;j<W;j++){ 45 scanf("%d",&field[i][j]); 46 } 47 } 48 49 for(int i=0;i<51;i++){ 50 for(int j=0;j<10;j++){ 51 for(int k=0;k<10;k++){ 52 for(int l=0;l<10;l++){ 53 fill(d[i][j][k][l],d[i][j][k][l]+10,INF); 54 } 55 } 56 } 57 } 58 59 priority_queue<State> que; 60 for(int i=0;i<W;i++){ 61 int no = o-1, nd = 0; 62 if(field[0][i]<0) nd -= field[0][i]; 63 else no = min(m, no+field[0][i]); 64 if(no<=0) continue; 65 d[no][0][i][i][i] = nd; 66 que.push((State){nd,no,0,i,i,i}); 67 } 68 69 int ans = -1; 70 while(que.size()){ 71 State p = que.top(); que.pop(); 72 if(d[p.o][p.y][p.x][p.l][p.r]<p.d) continue; 73 if(p.d>=f)break; 74 if(p.y==H-1){ 75 ans = p.d; 76 break; 77 } 78 79 for(int i=0;i<3;i++){ 80 int nx = p.x + dx[i], ny = p.y + dy[i]; 81 if(nx<0||W<=nx||ny<0||H<=ny) continue; 82 int nl = min(p.l, nx), nr = max(p.r, nx); 83 int no = p.o - 1; 84 int nd = p.d; 85 if(i==2){ 86 nl = nx; nr = nx; 87 } 88 if(i==2 || nx < p.l || p.r < nx){ 89 if(field[ny][nx]<0) nd -= field[ny][nx]; 90 else no = min(m, no+field[ny][nx]); 91 } 92 if(no <= 0) continue; 93 if(d[no][ny][nx][nl][nr] > nd){ 94 d[no][ny][nx][nl][nr] = nd; 95 que.push((State){nd, no, ny, nx, nl, nr}); 96 } 97 } 98 } 99 if(ans==-1) cout << "NA" << endl; 100 else cout << ans << endl; 101 } 102 103 return 0; 104}
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/06/18 03:24