My code below:
Code: Select all
#include<iostream>
#include<cstring>
#define M 1000000
#define INF 999999
using namespace std;
int dx[4]={-1,+1,0,0};
int dy[4]={0,0,-1,+1};
int A[999][999];
int row,col;
struct node {
node* next;
//node* pre;
int index;
int weight;
};
class PQueue {
node* head;
public:
PQueue(){
head=NULL;
}
void add_with_priority(int key,int value) {
node* newNode=new node;
newNode->next=NULL;
newNode->index=key;
newNode->weight=value;
if(head==NULL) {
head=newNode;
}
if(head!=NULL) {
node* prev=head;
bool flag=false;
node* cur=head;
if(head->weight>newNode->weight) {
head=newNode;
prev=newNode;
newNode->next=cur;
}
else {
while(cur!=NULL) {
//cout<<cur->weight<<endl;
if(cur->index==newNode->index) {
cur->weight=newNode->weight;
flag=true;
break;
}
if(cur->weight>newNode->weight) {
prev->next=newNode;
newNode->next=cur;
flag=true;
break;
}
prev=cur;
cur=cur->next;
}
if(flag==false) {
prev->next=newNode;
}
}
}
}
int pop() {
node* temp=new node;
temp=head;
int key=temp->index;
head=head->next;
delete temp;
return key;
}
int IsEmpty(){
if(head==NULL) return 1;
return 0;
}
void print() {
node* cur=head;
while(cur!=NULL) {
cout<<cur->index<<" ";
cout<<cur->weight<<endl;
cur=cur->next;
}
}
};
int BFS() {
int visited[M];
int dis[M];
PQueue q;
for(int i=0;i<row*col;i++)
{
dis[i]=INF;
q.add_with_priority(i,INF);
visited[i]=0;
}
dis[0]=0;
q.add_with_priority(0,0);
int x,y,w,c,p;
while(!q.IsEmpty()) {
p=q.pop();
if(p==((row*col)-1)) break;
if(visited[p]==0) {
x=p/col;
y=p%col;
for(int i=0;i<4;i++) {
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=0 && tx<row && ty>=0 && ty<col) {
w=A[tx][ty];
c=(tx*col)+ty;
if(dis[c]>dis[p]+w) {
dis[c]=dis[p]+w;
//cout<<"dis["<<c<<"]="<<dis[c]<<endl;
q.add_with_priority(c,dis[c]);
}
//q.add_with_priority(c,dis[c]);
}
}
visited[p]=1;
}
}
return dis[(row*col)-1];
}
int main()
{
int test,node;
cin>>test;
while(test--) {
cin>>row>>col;
for(int i=0;i<row;i++) {
for(int j=0;j<col;j++) {
cin>>A[i][j];
}
}
cout<<BFS()<<endl;;
}
return 0;
}
