zju 2935 Here We Go(relians) Again

//最短路径  关键是构图

#include
const int maxint=9999999;
char ch[10];
bool s[455];
int dist[455],c[455][455];
void Dijkstra(int n,int v,int dist[],int c[][455])
{
     int i,j,temp,newdist,u;
// n顶点的个数    v 原点
   for(i=1;i<=n;i++)
   {
   dist[i]=c[v][i];
   s[i]=false;             
   }      
   dist[v]=0;s[v]=true;
   for(i=1;i   {
    temp=maxint;
    u=v;
    for(j=1;j<=n;j++)
      if(!s[j]&&dist[j]      {
      u=j;temp=dist[j];                      
      }
    s[u]=true;
    for(j=1;j<=n;j++)
    if(!s[j]&&c[u][j]    {
    newdist=dist[u]+c[u][j];
      if(newdist      {
      dist[j]=newdist;                  
      }                       
    }
   }
}

int main()
{
    int m,n,dis,i,j;
  while(scanf("%d%d",&m,&n)&&m&&n)
  {
     for(i=1;i<=(m+1)*(n+1);i++)
     {
     for(j=1;j<=(m+1)*(n+1);j++)
     c[i][j]=maxint;               
     }
   for(i=0;i   {
     //读横的
     for(j=1;j<=n;j++)
     {
     scanf("%d%s",&dis,ch);     
     if(dis==0)
     {c[(n+1)*i+j][(n+1)*i+j+1]=maxint;c[(n+1)*i+j+1][(n+1)*i+j]=maxint;continue;}  
     dis=2520/dis;       
     if(*ch=='>') c[(n+1)*i+j][(n+1)*i+j+1]=dis;
     else if(*ch=='*') {c[(n+1)*i+j][(n+1)*i+j+1]=dis;c[(n+1)*i+j+1][(n+1)*i+j]=dis;}
     else if(*ch=='<') c[(n+1)*i+j+1][(n+1)*i+j]=dis;
     else c[(n+1)*i+j][(n+1)*i+j+1]=maxint;
     }
     //读树的
     for(j=1;j<=n+1;j++)
     {
     scanf("%d%s",&dis,ch);       
     if(dis==0)
     {c[(n+1)*i+j][(n+1)*i+j+n+1]=maxint;c[(n+1)*i+j+n+1][(n+1)*i+j]=maxint;continue;}     
     dis=2520/dis;
     if(*ch=='v') c[(n+1)*i+j][(n+1)*i+j+n+1]=dis;
     else if(*ch=='*') {c[(n+1)*i+j][(n+1)*i+j+n+1]=dis;c[(n+1)*i+j+n+1][(n+1)*i+j]=dis;}
     else if(*ch=='^')  c[(n+1)*i+j+n+1][(n+1)*i+j]=dis;
     else c[(n+1)*i+j][(n+1)*i+j+n+1]=maxint;                       
     }
   } 
     for(j=1;j<=n;j++)
     {
     scanf("%d%s",&dis,ch);       
     if(dis==0)
     {c[(n+1)*i+j][(n+1)*i+j+1]=maxint;c[(n+1)*i+j+1][(n+1)*i+j]=maxint;continue;} 
     dis=2520/dis;     
     if(*ch=='>') c[(n+1)*i+j][(n+1)*i+j+1]=dis;
     else if(*ch=='*') {c[(n+1)*i+j][(n+1)*i+j+1]=dis;c[(n+1)*i+j+1][(n+1)*i+j]=dis;}
     else if(*ch=='<') c[(n+1)*i+j+1][(n+1)*i+j]=dis;
     else c[(n+1)*i+j][(n+1)*i+j+1]=maxint;
     }
     /*
     for(i=1;i<=(m+1)*(n+1);i++)
     {
     for(j=1;j<=(m+1)*(n+1);j++)
     printf("%d  ",c[i][j]);
     printf("\n");                
     }
     */           
     Dijkstra((m+1)*(n+1),1,dist,c);
     if(dist[(m+1)*(n+1)]==maxint)
     printf("Holiday\n");
     else printf("%d blips\n",dist[(m+1)*(n+1)]);                
  }   
}