学步园

题意：给你一个迷宫，告诉你原点，然后求走出迷宫的最少花费。

感觉优先队列好神奇，本来是用dfs的，但是老是RE，但是用了优先队列就过了。

优先队列的使用格式大概是：

头文件：

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

然后是命名：priority_que<int,vector<int>,cmp> q;

这里有比较函数：

struct cmp

{

bool operator（）(int x,int y)

{   return XXXXXXX;}   //这里自己比较啦。拿什么东西比较都可以。

}

 其他思想差不多啦。每次都把四个方向还没有走过的格子放到队列里面去，然后每次用的时候取出队列中花费最小的那个队列，然后继续比较。

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define maxn 1010
#define inf 0x3f3f3f3f
char map[maxn][maxn];
int mapp[maxn][maxn];
int vis[maxn][maxn];
int cho[4]={1,0,-1,0};
int choo[4]={0,1,0,-1};
int bl[maxn];
int ans;
int n,m,num;
int cos[maxn*maxn];
struct cmp
{
    bool operator()(int x,int y)
    {
        return cos[x]>cos[y];
    }
};

int min(int x,int y)
{
    if(x>y) return y;
    else return x;
}
void dfs(int x,int y,int sum)
{
    if(x==0||x==m-1||y==0||y==n-1) {ans=min(ans,sum);return;}
    int i,j,k;
    int tmp=inf,flag;
    for(i=0;i<4;i++)
    {
        int xx=x+cho[i];
        int yy=y+choo[i];
        if(!vis[xx][yy]&&tmp>mapp[xx][yy])
        {
            tmp=mapp[xx][yy];
            flag=i;
        }
    }
  //  printf("xx=%d  yy=%d\n",x+cho[flag],y+choo[flag]);
    vis[x+cho[flag]][y+choo[flag]]=1;
    dfs(x+cho[flag],y+choo[flag],sum+tmp);
}
void init()
{
    int i,j,k;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            {vis[i][j]=0;cos[i*n+j]=0;}
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=inf;
        scanf("%d%d%d",&num,&n,&m);
      //  printf("num=%d\n",num);
        init();
        int i,j,k;
        for(i=0;i<num;i++)
        {
            char a;
            int b;
            getchar();
            scanf("%c %d",&a,&b);
            bl[a]=b;
     //       printf("%c   %d\n",a,b);
        }
        getchar();
        int inx,iny;
        for(i=0;i<m;i++)
            {
                gets(map[i]);
                for(j=0;j<n;j++)
                    {
                        if(map[i][j]=='E')
                        {vis[i][j]=1;inx=i;iny=j;}
                        mapp[i][j]=bl[map[i][j]];
                    }
            }


        //dfs(inx,iny,0);
        priority_queue<int, vector<int>, cmp> que;
        int inz=inx*n+iny;
        cos[inz]=0;
        que.push(inz);
        while(!que.empty())
        {
            int tmpz=que.top();
            que.pop();
            int x=tmpz/n,y=tmpz%n;
            //printf("????\n");
         //   printf("x=%d  y=%d\n",x,y);
            if(x==0||x==m-1||y==0||y==n-1) {ans=cos[tmpz];break;}
            for(i=0;i<4;i++)
            {
                int xx=x+cho[i],yy=y+choo[i];
                int zz=xx*n+yy;
                if(xx>-1&&xx<m&&y>-1&&y<n&&!vis[xx][yy])
                {
                    cos[zz]=cos[tmpz]+mapp[xx][yy];
               //     printf("***cos[zz]=%d\n",cos[zz]);
                    que.push(zz);
                    vis[xx][yy]=1;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}