#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
#define INF 100000
#define pii pair<pair<int,int>,int>
struct comp {
bool operator() (const pii &a, const pii &b) {
return a.second > b.second;
}
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n,m;
int cost[110][110];
bool isvalid(int x,int y) {
if(x < 0 || y<0 || x> n-1 || y > m-1)
return false;
return true;
}
void dijakstra(int destx,int desty,int total_time) {
priority_queue < pii, vector<pii> , comp> que;
int d[110][110];
int state[110][110];
memset(d,INF,sizeof(d));
memset(state,0,sizeof(state));
d[0][0]=0;
que.push(make_pair(make_pair(0,0),cost[0][0]));
state[0][0]=1;
while(!que.empty()) {
int xc=que.top().first.first;
int yc=que.top().first.second;
int w=que.top().second;
// printf("%d %d %d\n",xc,yc,w);
if(xc==destx && yc==desty) {
break;
}
que.pop();
for(int j=0;j<4;j++) {
int x1=xc+dx[j];
int x2=yc+dy[j];
if(isvalid(x1,x2) && !state[x1][x2] && (w+cost[x1][x2])<=total_time)
{
d[x1][x2]=w+cost[x1][x2];
state[x1][x2]=1;
que.push(make_pair(make_pair(x1,x2),d[x1][x2]));
}
}
}
if(state[destx][desty]==0)
printf("NO\n");
else
{
printf("YES\n");
// printf("%d %d\n",total_time,d[destx][desty]);
printf("%d\n",(total_time-d[destx][desty]));
}
}
int main() {
int i,j,a,b,c,t;
// freopen("in1.txt","r",stdin);
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(i=0;i<n;i++) {
for(j=0;j<m;j++) {
scanf("%d",&cost[i][j]);
}
}
int destx,desty,tc;
scanf("%d%d%d",&destx,&desty,&tc);
dijakstra(destx-1,desty-1,tc);
}
return 0;
}
sir plz check my code i can't understand why i am getting WA.
Thanks
