本文共 1845 字，大约阅读时间需要 6 分钟。
题意：给一个方阵表示一个湖每个格子代表那个位置的风向，顺风走不要花费否则花费为1。给你起点重点问你最小花费是多少？
思路：这道题写的四不像，先spfa写了一下T，然后bfs又T。接着加了个优先队列就过了。。。主要就是类似于spfa dis数组记录到那点的最小花费。然后只要能更新就入队。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define PB(a) push_back(a)13 14 using namespace std;15 16 typedef long long ll;17 typedef pair pii;18 typedef pair puu;19 typedef pair pid;20 typedef pair pli;21 typedef pair pil;22 23 const int INF = 0x3f3f3f3f;24 const double eps = 1e-6;25 const int LEN = 1002;26 int Map[LEN][LEN], n, m, dis[LEN][LEN];27 int xx[] = {-1,-1, 0, 1, 1, 1, 0,-1};28 int yy[] = { 0, 1, 1, 1, 0,-1,-1,-1};29 struct P { int x, y, st;};30 struct cmp31 {32 bool operator() (P a, P b){ return a.st>b.st;}33 };34 35 P temp;36 37 int bfs(int x, int y, int ex, int ey)38 {39 temp.x = x;temp.y = y;temp.st = 0;40 priority_queue , cmp> q;41 int ret = INF;42 q.push(temp);43 register int tx, ty, i;44 memset(dis, 0x3f, sizeof dis);45 dis[x][y] = 0;46 while(!q.empty()){47 P vex = q.top();q.pop();48 if(vex.x==ex && vex.y==ey) { return vex.st;}49 for(i=0; i<8; i++){50 tx = vex.x+xx[i];51 ty = vex.y+yy[i];52 temp.st = vex.st+(i==Map[vex.x][vex.y]?0:1);53 if(tx>=0 && tx =0 && ty temp.st){54 temp.x = tx;temp.y = ty;55 dis[tx][ty] = temp.st;56 q.push(temp);57 }58 }59 }60 }61 62 void read(int &ret)63 {64 char c;65 while((c = getchar())<'0' || c>'9');66 ret = 0;67 while(c>='0' && c<='9'){68 ret = ret*10+(c-'0');69 c = getchar();70 }71 }72 73 int main()74 {75 // freopen("in.txt", "r", stdin);76 77 int q, sx, sy, ex, ey, ans;78 while(scanf("%d%d", &n, &m)!=EOF){79 getchar();80 for(int i=0; i
转载于:https://www.cnblogs.com/shu-xiaohao/p/3533870.html
