题目大意：给出一个矩阵，每个格子有不同的消耗，给出起点和终点，求从起点走到终点要求消耗最小的路径。
例如：
思路：其实就是求矩阵的最短路径。也就是dijkstra算法，实现方法有很多，可以用一个矩阵记录每个点到起点的消耗（初始化为无穷大），搜索，若有更小的则更新；再一种是直接用优先队列来求，这保证了每一步都是最优的，时间复杂度和空间复杂度都比上一种方法更优，下面代码便是用这种方法。
PS：关于最短路径算法dijkstra,最关键的理解我认为是从起点开始，直接相连的初始化为各自路径大小，其他的为无穷大，下一步就选最小的那个，同时更新其它的点到起点的路径大小。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <memory.h> 5 using namespace std; 6 7 struct Node 8 { 9 int r,c; 10 int cost; 11 friend bool operator <(Node a,Node b) 12 { 13 return a.cost>b.cost; 14 } 15 }; 16 int main() 17 { 18 int t; 19 cin>>t; 20 while(t--) 21 { 22 int n,m; 23 cin>>n>>m; 24 int matrix[n+1][m+1]; 25 bool v[n+1][m+1]; 26 memset(v,false,sizeof(v)); 27 int f[8]={-1,0,0,1,1,0,0,-1}; 28 for(int i=1;i<n+1;i++) 29 for(int j=1;j<m+1;j++) 30 scanf("%d",&matrix[i][j]); 31 int sx,sy,dx,dy; 32 cin>>sx>>sy>>dx>>dy; 33 priority_queue<Node> q; 34 Node s; 35 s.r=sx; 36 s.c=sy; 37 s.cost=matrix[s.r][s.c]; 38 Node now=s; 39 int row,col; 40 while(!(now.r==dx&&now.c==dy)){ 41 for(int i=0;i<8;i+=2){ 42 row=now.r+f[i]; 43 col=now.c+f[i+1]; 44 if(row>0&&row<n+1&&col>0&&col<m+1&&!v[row][col]) 45 { 46 Node next; 47 next.r=row; 48 next.c=col; 49 next.cost=now.cost+matrix[row][col]; 50 q.push(next); 51 } 52 } 53 now=q.top(); //这里要注意一下，不能直接q.pop()再直接取得头部，这样会超时，因为有一些节点我们已经找到了 54 //最短路径，可是队列里仍存在我们以前push进去的未更新的节点，直接pop的话会重复做很多工作 55 while(v[now.r][now.c]){ 56 q.pop(); 57 now=q.top(); 58 } 59 v[now.r][now.c]=true; 60 } 61 cout<<now.cost<<endl; 62 } 63 return 0; 64 }