Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

2个完全一样的函数一个能AC一个WA,哪位同学能看出问题来~~~

Posted by hao2 at 2009-03-09 20:57:21 on Problem 1273

OMG,WA20多次了啊~我打死也想不通啊~~~
A:这个不能过
void Dijkstra()
{
int mindis,i,j,u;
int s[MAXN];
for(i=1;i<=N;i++)
   {
   dis[i]=map[1][i];
   s[i]=0;
   if(i!=1&&dis[i]>0)
     pre[i]=1;
   else
     pre[i]=-1;
   }
s[1]=1;
for(i=2;i<=N;i++)
   {
   mindis=0;
   for(j=1;j<=N;j++)
      {
      if(s[j]==0&&dis[i]>mindis)
         {
         u=j;
         mindis=dis[j];
         }
      }
   if(mindis==0)
     return;
   s[u]=1;
   for(j=1;j<=N;j++)
      {
      if(s[j]==0&&map[u][j]>0&&dis[u]+map[u][j]>dis[j])
        {
        dis[j]=dis[u]+map[u][j];
        pre[j]=u;
        }
      }
   }
}

B:这个能过
    void Dijkstra()
    {
    int mindis,i,j,u;
    int s[MAXN];
    for(i=1;i<=N;i++)
        {
        dis[i]=map[1][i];
        s[i]=0;
        if(i!=1&&dis[i]>0)
           pre[i]=1;
        else 
           pre[i]=-1;
        }
    s[1]=1;
    for(i=2;i<=N;i++)
        {
        mindis=0;
        for(j=1;j<=N;j++)
           {
           if(s[j]==0&&dis[j]>mindis)
              {
              u=j;
              mindis=dis[j];
              }
            }
        if(mindis==0)
          return;
        s[u]=1;
        for(j=1;j<=N;j++)
           {
           if(s[j]==0&&map[u][j]>0&&dis[u]+map[u][j]>dis[j])
              {
              dis[j]=dis[u]+map[u][j];
              pre[j]=u;
              }
           }
         }
     }
如果看出来了请告诉我,万分感谢

Followed by:

小童鞋，看在你在我家乡上学的面子上回答你吧…… (115) tester000 2009-03-09 22:31:31
- Re:小童鞋，看在你在我家乡上学的面子上回答你吧…… (127) hao2 2009-03-10 17:04:06
  - Re:大哥神眼啊~不仅帮我把程序问题看出来了,还把我在哪里上学也看出来了~~~ (0) hao2 2009-03-10 17:07:39
    - Re:万分感谢啊~昨天我3个同学纯肉眼strcmp都没看出来...知识地力量果然是强大的哈...我愿爬上NEFU的主楼卸下楼顶的破红星献给大侠(马屁乱拍...看不下去了) (0) hao2 2009-03-10 17:13:26
      - 小童鞋果然年轻气盛……有卸破星星的力气还是去多A几个题吧……至于感谢么，你还是感谢BeyondCompare的作者吧…… (0) tester000 2009-03-10 18:38:00
Re:深搜TLE，Dijstra就AC，真郁闷！！！！！！！！！！！！！！！！ (100) jsmingzi 2009-11-02 20:37:36

Post your reply here:

User ID:
Password:
Title:

Content:

> OMG,WA20多次了啊~我打死也想不通啊~~~
> A:这个不能过
> void Dijkstra()
> {
> int mindis,i,j,u;
> int s[MAXN];
> for(i=1;i<=N;i++)
>    {
>    dis[i]=map[1][i];
>    s[i]=0;
>    if(i!=1&&dis[i]>0)
>      pre[i]=1;
>    else
>      pre[i]=-1;
>    }
> s[1]=1;
> for(i=2;i<=N;i++)
>    {
>    mindis=0;
>    for(j=1;j<=N;j++)
>       {
>       if(s[j]==0&&dis[i]>mindis)
>          {
>          u=j;
>          mindis=dis[j];
>          }
>       }
>    if(mindis==0)
>      return;
>    s[u]=1;
>    for(j=1;j<=N;j++)
>       {
>       if(s[j]==0&&map[u][j]>0&&dis[u]+map[u][j]>dis[j])
>         {
>         dis[j]=dis[u]+map[u][j];
>         pre[j]=u;
>         }
>       }
>    }
> }
> 
> B:这个能过
>     void Dijkstra()
>     {
>     int mindis,i,j,u;
>     int s[MAXN];
>     for(i=1;i<=N;i++)
>         {
>         dis[i]=map[1][i];
>         s[i]=0;
>         if(i!=1&&dis[i]>0)
>            pre[i]=1;
>         else 
>            pre[i]=-1;
>         }
>     s[1]=1;
>     for(i=2;i<=N;i++)
>         {
>         mindis=0;
>         for(j=1;j<=N;j++)
>            {
>            if(s[j]==0&&dis[j]>mindis)
>               {
>               u=j;
>               mindis=dis[j];
>               }
>             }
>         if(mindis==0)
>           return;
>         s[u]=1;
>         for(j=1;j<=N;j++)
>            {
>            if(s[j]==0&&map[u][j]>0&&dis[u]+map[u][j]>dis[j])
>               {
>               dis[j]=dis[u]+map[u][j];
>               pre[j]=u;
>               }
>            }
>          }
>      }
> 如果看出来了请告诉我,万分感谢

Home Page Go Back To top