Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么错了呢?????????????????????????????????

Posted by 20110531 at 2011-11-08 14:21:20 on Problem 3037
#include<iostream>
#include<cstdio>
#include<string>
#include<iomanip>
#include<queue>
#include<cmath>
#define x 101
#define z 10100
#define inf 99999999999999.0
using namespace std;
double v[x][x];//记录各点的速度 
int mn[z];//记录结构体中相应元素位置 
bool flag[z];//记录是不是在队列中 
double d[z];//记录到达各点的时间 
queue <int> q;
int m,n;//行数,列数 
struct node
{
   int end;
   int next;
   double time;
}E[40010];//记录边 
void spfa()
{
   int i,y;
   memset(flag,0,sizeof(flag));
   d[1]=0;
   q.push(1);
   flag[1]=1;
   while(!q.empty())
   {
     y=q.front();
     q.pop();
     flag[y]=0;
     for(i=mn[y];i;i=E[i].next)
     {
        int temp=E[i].end;
        if(d[temp]>d[y]+E[i].time)
        {
           d[temp]=d[y]+E[i].time;
           if(!flag[temp])
           {
              q.push(temp);
              flag[temp]=1;
           }
        }
     }
   }
   printf("%.2lf\n",d[m*n]);
}
int main()
{
   int i,j,b,c,k;
   while(scanf("%lf %d %d",&v[1][1],&m,&n)!=EOF)
   {
     scanf("%d",&b);   
   for(i=1;i<=m;++i)
     for(j=1;j<=n;++j)
     {
        if(i==1&&j==1)continue;
       scanf("%d",&c);
       v[i][j]=v[1][1]*pow(2.0,b-c);
     }
     
     memset(mn,0,sizeof(mn));
     k=0;
     for(i=1;i<=m;++i)
      for(j=1;j<=n;++j)
       {
         d[(i-1)*n+j]=inf;
         if(i-1>0)
         {
           ++k;
           E[k].end=(i-2)*n+j;
           E[k].time=1.0/v[i][j];
           E[k].next=mn[(i-1)*n+j];
           mn[(i-1)*n+j]=k;
         }
         if(i+1<m+1)
         {
            ++k;
            E[k].end=i*n+j;
            E[k].time=1.0/v[i][j];
            E[k].next=mn[(i-1)*n+j];
            mn[(i-1)*n+j]=k;
         }
         if(j>1)
         {
            ++k;
            E[k].end=(i-1)*n+j-1;
            E[k].time=1.0/v[i][j];
            E[k].next=mn[(i-1)*n+j];
            mn[(i-1)*n+j]=k;
         }
         if(j<n)
         {
            ++k;
            E[k].end=(i-1)*n+j+1;
            E[k].time=1.0/v[i][j];
            E[k].next=mn[(i-1)*n+j];
            mn[(i-1)*n+j]=k;
         }
       }
       spfa();
     }
     system("pause");
     return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator