优先队列广搜，有人说用SPFA，不知道怎么做的
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std; #define MAX_COORDINATE 205
#define inf 0x3f3f3f3f
#define EDGE 200 struct Grid
{
int left, right, up, down;
}grid[MAX_COORDINATE][MAX_COORDINATE]; // using down-left coner point to present a gird struct Point
{
int x, y;
int door_cnt;
Point()
{}
Point(int xx, int yy, int dd):x(xx), y(yy), door_cnt(dd)
{}
}nemo; int wall_num, door_num;
bool vis[MAX_COORDINATE][MAX_COORDINATE]; bool operator < (const Point &a, const Point &b)
{
return a.door_cnt > b.door_cnt;
} void make_grids(int x, int y, int direction, int value)
{
if (direction == )
{
grid[x][y].down = value;
grid[x][y - ].up = value;
}else
{
grid[x][y].left = value;
grid[x - ][y].right = value;
}
} void build_wall(int x, int y, int direction, int length)
{
for (int i = ; i < length; i++)
{
int current_x = x;
int current_y = y;
if (direction == )
current_x += i;
else
current_y += i;
make_grids(current_x, current_y, direction, inf);
}
} void init_grids()
{
for (int i = ; i < EDGE; i++)
{
grid[i][].down = inf;
grid[i][EDGE - ].up = inf;
grid[][i].left = inf;
grid[EDGE - ][i].right = inf;
}
} void input()
{
memset(grid, , sizeof(grid));
init_grids();
for (int i = ; i < wall_num; i++)
{
int x, y, direction, length;
scanf("%d%d%d%d", &x, &y, &direction, &length);
build_wall(x, y, direction, length);
}
for (int i = ; i < door_num; i++)
{
int x, y, direction;
scanf("%d%d%d", &x, &y, &direction);
make_grids(x, y, direction, );
}
double x, y;
scanf("%lf%lf", &x, &y);
nemo.x = floor(x);
nemo.y = floor(y);
} int work()
{
if (nemo.x < || nemo.x >= EDGE || nemo.y < || nemo.y >= EDGE)
return ;
priority_queue<Point> pq;
pq.push(Point(, , ));
memset(vis, , sizeof(vis));
vis[][] = true;
while (!pq.empty())
{
Point u = pq.top();
if (u.x == nemo.x && u.y == nemo.y)
return u.door_cnt;
pq.pop();
if (grid[u.x][u.y].up != inf && !vis[u.x][u.y + ])
{
pq.push(Point(u.x, u.y + , u.door_cnt + grid[u.x][u.y].up));
vis[u.x][u.y + ] = true;
}
if (grid[u.x][u.y].down != inf && !vis[u.x][u.y - ])
{
pq.push(Point(u.x, u.y - , u.door_cnt + grid[u.x][u.y].down));
vis[u.x][u.y - ] = true;
}
if (grid[u.x][u.y].left != inf && !vis[u.x - ][u.y])
{
pq.push(Point(u.x - , u.y, u.door_cnt + grid[u.x][u.y].left));
vis[u.x - ][u.y] = true;
}
if (grid[u.x][u.y].right != inf && !vis[u.x + ][u.y])
{
pq.push(Point(u.x + , u.y, u.door_cnt + grid[u.x][u.y].right));
vis[u.x + ][u.y] = true;
}
}
return -;
} int main()
{
while (scanf("%d%d", &wall_num, &door_num), !(wall_num == - && door_num == -))
{
input();
printf("%d\n", work());
}
return ;
}