HDU 3152 Obstacle Course(优先队列) - c++编程基础

Problem Description

You are working on the team assisting with programming fZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgTWFycyByb3Zlci4gVG8gY29uc2VydmUgZW5lcmd5LCB0aGUgcm92ZXIgbmVlZHMgdG8gZmluZCBvcHRpbWFsIHBhdGhzIGFjcm9zcyB0aGUgcnVnZ2VkIHRlcnJhaW4gdG8gZ2V0IGZyb20gaXRzIHN0YXJ0aW5nIGxvY2F0aW9uIHRvIGl0cyBmaW5hbCBsb2NhdGlvbi4gVGhlIGZvbGxvd2luZyBpcyB0aGUgZmlyc3QgYXBwcm94aW1hdGlvbgogZm9yIHRoZSBwcm9ibGVtLjxicj4KPGJyPgo8Y2VudGVyPjxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/49/1_ac9yl__.jpg" alt="\">
N * N square matrices contain the expenses for traversing each individual cell. For each of them, your task is to find the minimum-cost traversal from the top left cell [0][0] to the bottom right cell [ N-1][ N-1]. Legal moves are up, down, left, and right; that is, either the row index changes by one or the column index changes by one, but not both.

Input Each problem is specified by a single integer between 2 and 125 giving the number of rows and columns in the N * N square matrix. The file is terminated by the case N = 0.

Following the specification of N you will find N lines, each containing N numbers. These numbers will be given as single digits, zero through nine, separated by single blanks.

Output Each problem set will be numbered (beginning at one) and will generate a single line giving the problem set and the expense of the minimum-cost path from the top left to the bottom right corner, exactly as shown in the sample output (with only a single space after "Problem" and after the colon).

Sample Input

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

Sample Output

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

Source 2008 ACM-ICPC Pacific Northwest Region

给你一副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