给出一个地图，地图有四种路面，经过每种路面花费的时间不同，问从起点到终点所花费的最少时间是多少

把到各个点的花费存入队列中，然后弹出，即可得到最小 

 

Sample Input

4 6 1 2 10 T...TT TTT### TT.@#T ..###@ 0 1 3 0 4 6 1 2 2 T...TT TTT### TT.@#T ..###@ 0 1 3 0 2 2 5 1 3 T@ @. 0 0 1 1

 

 

Sample Output

Case 1: 14 Case 2: 8 Case 3: -1

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int x,y,v1,v2,v3,b,n,m;int x1,x2,y1,y2;int p[25][25];int vis[25][25];int v[5];int dir[4][2] = {
    {1,0},{-1,0},{0,1},{0,-1}};struct node{    int x,y,step;    friend bool operator < (node a,node b)    {        return a.step > b.step;    }};bool judge(int x,int y){    if(x < 0 || y < 0 || x >= n || y >= m || p[x][y] < 0 || vis[x][y])        return false;    return true;}int work(){    priority_queue
         
          que;    node a,b;    a.x=x1;    a.y=y1;    a.step = 0;    que.push(a);    memset(vis,0,sizeof(vis));    vis[x1][y1] = 1;    while(!que.empty())    {        a = que.top();        que.pop();        if(a.x == x2 && a.y == y2)                return a.step;        for(int i = 0;i < 4;i++)        {            b = a;            b.x += dir[i][0];            b.y += dir[i][1];            if(!judge(b.x,b.y))                continue;            b.step  += v[p[b.x][b.y]];            vis[b.x][b.y] = 1;            que.push(b);        }    }    return -1;}int main(){    int i,j,cas = 1;    char s[1000];    while(~scanf("%d%d",&n,&m))    {        scanf("%d%d%d",&v[3],&v[2],&v[1]);        for(i = 0; i < n; i++)        {            scanf("%s",s);            for(j = 0;s[j]; j++)            {                if(s[j]=='T') p[i][j] = 1;                else if(s[j] == '.') p[i][j] = 2;                else if(s[j] == '#') p[i][j] = 3;                else if(s[j] == '@') p[i][j] = -1;            }        }        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);        int ans = work();        printf("Case %d: %d\n",cas++,ans);    }    return 0;}