最短路径有关问题（BFS）

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 1000;
struct locat{
    int x;
    int y;
    int sum;  ///存放当前到达此处最小值
    int pre;  ///原始值，不变的。
    bool mark;///标记此处已经访问过，即sum的值已经改变。
    locat(){
        mark = false;
    }
};

locat map1[maxn][maxn];
int m, n;
int ex, ey;///目的地点。

void init(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &map1[i][j].pre);
            map1[i][j].sum = map1[i][j].pre; ///初始化
            map1[i][j].x = i;
            map1[i][j].y = j;
        }
    }
    scanf("%d%d", &ex, &ey);
}

void work() {
    locat tmp;
    locat tmp1;
    queue<locat> q;
    q.push(map1[1][1]);
    while(q.empty()!=true) {
        tmp = q.front();
        tmp1 = tmp; ///保存tmp的值，在向右走的时候用。
        q.pop();
        if(tmp.x<m){ ///判断是否越界，否则向下走。
            if(map1[tmp.x+1][tmp.y].mark == false) { ///第一次访问
                tmp.sum = tmp.sum + map1[tmp.x+1][tmp.y].pre;
                map1[tmp.x+1][tmp.y].sum = tmp.sum;
                q.push(tmp);
                map1[tmp.x+1][tmp.y].mark = true;
            }
            else{///第二次访问
                map1[tmp.x+1][tmp.y].sum = min(map1[tmp.x+1][tmp.y].sum, map1[tmp.x][tmp.y].sum + map1[tmp.x+1][tmp.y].pre);
              /*  if(tmp.x+1 == ex && tmp.y == ey) {
                    break;
                }
                */
                q.push(map1[tmp.x+1][tmp.y]);
            }
        }
        if(tmp1.y<n) {
            if(map1[tmp1.x][tmp1.y+1].mark == false) {
                tmp1.sum = tmp1.sum + map1[tmp1.x][tmp1.y+1].pre;
                map1[tmp1.x][tmp1.y+1].sum = tmp1.sum;
                q.push(tmp1);
                map1[tmp1.x][tmp1.y+1].mark = true;
            }
            else{
                map1[tmp1.x][tmp1.y+1].sum = min(map1[tmp1.x][tmp1.y+1].sum, map1[tmp1.x][tmp1.y].sum+map1[tmp1.x][tmp.y+1].pre);
               /* if(tmp1.x == ex && tmp1.y+1 == ey) {
                    break;
                }
                */
                q.push(map1[tmp1.x][tmp1.y+1]);
            }
        }
    }
}

int main()
{
    init();
    work();
    printf("%d\n", map1[ex][ey].sum);
    return 0;
}

/********************************
题目：从（1,1）到（m，n）的最短路径。
测试数据：
输入：
4 4
1 2 3 4
5 1 2 5
2 1 8 9
1 1 1 1
4 4
输出：
8
********************************/