最短路径问题（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 41 2 3 45 1 2 52 1 8 91 1 1 14 4输出：8********************************/