HDU 3152 Obstacle Course(優先隊列)
Problem Description
You are working on the team assisting with programming fZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgTWFycyByb3Zlci4gVG8gY29uc2VydmUgZW5lcmd5LCB0aGUgcm92ZXIgbmVlZHMgdG8gZmluZCBvcHRpbWFsIHBhdGhzIGFjcm9zcyB0aGUgcnVnZ2VkIHRlcnJhaW4gdG8gZ2V0IGZyb20gaXRzIHN0YXJ0aW5nIGxvY2F0aW9uIHRvIGl0cyBmaW5hbCBsb2NhdGlvbi4gVGhlIGZvbGxvd2luZyBpcyB0aGUgZmlyc3QgYXBwcm94aW1hdGlvbgogZm9yIHRoZSBwcm9ibGVtLjxicj4KPGJyPgo8Y2VudGVyPjxpbWcgc3JjPQ=="http://www.2cto.com/uploadfile/Collfiles/20150209/20150209090742323.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_queueq; //優先隊列
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
