【BFS+priority_queue】hdu 4198

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4198
あなたに1枚の地図をあげて、“S”を起点にして、“#”は歩くことができなくて、1つの“.”を歩いて1つの単位の時間を必要として、1つの@“d+1の単位の時間を必要として、中起点を求めて地図の最短の時間を出ます......
アイデア:私の第一反応は分解点です......1つの"@"をd+1つに分解して、それからBFSしかしこのような写真の面倒です!
優先キュー+BFSで、経路長が短い点を先に拡張して、最短ルートを求めることができるのではないでしょうか.
私がBFSを書くのはすべて手作りの列です……やはりSTLをしっかり学ばなければなりません…

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010;
struct ty
{
    int x, y, time;
    friend bool operator < (ty a, ty b)
    {
        return a.time > b.time;
    }
};
priority_queue<ty> qu;
char map[N][N];
int visit[N][N];
int sx, sy, h, w, d;
const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int Bfs()
{
    ty now, next;
    while(!qu.empty()) qu.pop();

    now.x = sx;
    now.y = sy;
    now.time = 1;

    qu.push(now);
    visit[sx][sy]=1;

    while(!qu.empty())
    {
        now = qu.top();
        qu.pop();

        for(int i = 0; i < 4;i++)
        {
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];

            int x = next.x, y = next.y;
            if(x < 0 || x >= h || y < 0 || y >= w)
                return now.time;

            if(!visit[x][y] && map[x][y] != '#')
            {
                if(map[x][y] == '@') next.time = now.time + d + 1;
                    else next.time = now.time + 1;
                qu.push(next);
                visit[x][y] = 1;
            }
        }
    }
    return -1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &h, &w, &d);
        for(int i = 0; i < h; i++)
        {
            for(int j = 0; j < w; j++)
            {
                scanf(" %c", &map[i][j]);
                if(map[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
            }
       }

        memset(visit, 0 ,sizeof(visit));
        printf("%d
", Bfs());

    }
    return 0;
}