3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

Problem 1: 20
Problem 2: 19
Problem 3: 36

给你一副N*N的地图。

从左上角走到右下角，所经路程的最小花费。（数字即是花费）

因为不是求最短路径，而是求最少的花费。

可以用优先队列，花费小的优先级高。加上BFS，开个flag数字记录任意点的花费。

每次不断的更新flag数组的值，因为优先队列，每次弹出来的必然是优先级最高的（花费少的）

上代码

#include 
  
   
#include
   
     #include 
    
      #include 
     
       using namespace std; int n; int map[130][130]; int flag[130][130]; //记录到任意点的花费。 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; #define inf 0x6fffff struct node { int x,y; int cost; friend bool operator<(node a,node b) { return a.cost>b.cost; //优先队列，定义优先级，花费小的优先。 } } ; bool check(int x,int y) { if(x>=n ||y>=n ||x<0||y<0 ) return 0; return 1; } int bfs(int x,int y) { int i; node st,ed; priority_queue
      
       q; //优先队列 st.x=x; st.y=y; st.cost=map[0][0]; memset(flag,-1,sizeof(flag)); q.push(st); while(!q.empty()) { st=q.top(); //每次出来的都是最小的花费。 q.pop(); for(i=0;i<4;i++) { ed.x=st.x+dir[i][0]; ed.y=st.y+dir[i][1]; if(!check(ed.x,ed.y))//排除越界就够了，不用排除已经访问的，可以走回头路的，反正要遍历整个地图。 continue; ed.cost=st.cost+map[ed.x][ed.y]; if(ed.cost