优先队列

一般宽度优先搜素都是等距离的，经过每一点的时间都是1个单位。当经过某个点的时间不为1时，可以考虑优先队列。 如图所示： # 代表墙 X 代表护卫 。 代表路 r 代表人 a 代表天使 求解从人的位置到天使的位置最短时间，杀死一个护卫需要2个单位时间,人不止一个，可以看成多源BFS。

#include
#include
#include
#include
#include
using namespace std ;

char map[100][100] ;
int vis[100][100] = {0} ;

struct dot  {
    int x ;
    int y ;
    int t ;
};

bool operator<(dot x , dot y)   {
    return x.t > y.t ;
}
int m , n ;
priority_queue q ;


bool is_ok(dot cur) {
    if(cur.x < 0 || cur.x >=m || cur.y < 0 || cur.y >=n)
        return 0 ;
    return 1 ;
}

int dx[] = {0,1,0,-1} ;
int dy[] = {-1,0,1,0} ;

int bfs()   {
    while(!q.empty())   {
        dot cur = q.top() ;
        q.pop();
        if(map[cur.x][cur.y] == 'a')
            return cur.t ;
        dot next ;
        for(int i = 0 ; i < 4 ; i++)    {
            next.x = cur.x + dx[i] ;
            next.y = cur.y + dy[i] ;
            if(is_ok(next) && map[next.x][next.y] != '#' && !vis[next.x][next.y] ) {
                vis[next.x][next.y] = 1 ;
                if(map[next.x][next.y] == 'x')
                    next.t = cur.t + 2 ;
                else
                    next.t = cur.t + 1 ;
                q.push(next) ;
            }
        }
    }
    return -1 ;
}
int main()  {
    scanf("%d%d",&m,&n) ;
    for(int i = 0 ; i < m ; i++)
        scanf("%s",map[i]) ;
    int flag = 0 ;
    for(int i = 0 ; i < m ; i++)    {
        for(int j = 0 ; j < n ; j++)
            if(map[i][j] == 'r')    {
                map[i][j] = '.' ;
                dot cur ;
                cur.x = i ;
                cur.y = j ;
                cur.t = 0 ;
                vis[i][j] = 1 ;
                q.push(cur);
            }
    }
    int t = bfs() ;
    printf("%d
",t) ;
}