学步园

View Code

Problem : 3790 ( 最短路径问题 )     Judge Status : Accepted
RunId : 3819913    Language : G++    Author : tangcong506
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//#include<debug.h>
struct node
{
 int i;
 int j;
}map[1000][1000];
const int inf=0x7fffffff;
int visit[1010],dis[1010],P[1010],N,M;

struct Np
{
  int a;
  int b;
}C[1010];

int cmp(const void *p,const void *q)
{
  return (*(Np *)p).b > (*(Np *)q).b ? 1:-1;
}
   
void dij(int x,int y)
{
    int i,j,l=0;
   for(i=1;i<=N;i++)
   {
    dis[i]=inf;
    P[i]=inf;
    visit[i]=0;
   }
   dis[x]=0;
   P[x]=0;
   for(i=1;i<=N;i++)
   {
      int t=inf,k;
           for(j=0;j<=N;j++)
           {
             if(!visit[j]&&t>dis[j])
             {
                t=dis[j];
                k=j;
             }
          }
      visit[k]=1;
     for(j=1;j<=N;j++)
     {
         if(!visit[j]&&map[k][j].i!=inf&&dis[j]>dis[k]+map[k][j].i)
         {
          dis[j]=dis[k]+map[k][j].i;
          P[j]=P[k]+map[k][j].j;
         }
          else if(dis[k]+map[k][j].i== dis[j] )
              {
              
                        if( map[k][j].j + P[k] < P[j] )
                                 P[j]=map[k][j].j+P[k];
               }
     }
     }
         printf("%d %d\n",dis[y],P[y]);
}
   
    
int main( )
{
  //Debug();
 while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
 {
  int i,j,k,a,b,c,d,start,end;
  for(i=0;i<=N;i++)
   for(j=0;j<=N;j++)
    map[i][j].i=map[j][i].i=map[i][j].j=map[j][i].j=inf;
  for(i=0;i<M;i++)
  {
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if(map[a][b].i>c)
  {
  map[a][b].i=map[b][a].i=c;
  map[a][b].j=map[b][a].j=d;
  }
 }
 scanf("%d%d",&start,&end);
 dij(start,end);
}
//system("pause");
return 0;
}

这道题wrong.answer了好多次，不知道自己下面的错误的代码错在哪里。。打了好多测试数据都是对的。。。。最后改成了上面这样子才AC..郁闷 啊。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//#include<debug.h>
struct node
{
int i;
int j;
}map[1000][1000];
const int inf=0x7fffffff;
int visit[1010],dis[1010],P[1010],N,M;

struct Np
{
int a;
int b;
}C[1010];

int cmp(const void *p,const void *q)
{
return (*(Np *)p).b > (*(Np *)q).b ? 1:-1;
}

void dij(int x,int y)
{
int i,j,l=0;
for(i=1;i<=N;i++)
   {
    dis[i]=inf;
    P[i]=0;
    visit[i]=0;
   }
   dis[x]=0;
   P[x]=0;
for(i=1;i<=N;i++)
   {
int t=inf,k;
for(j=0;j<=N;j++)
           {
if(!visit[j]&&t>dis[j])
             {
                t=dis[j];
                k=j;
             }
          }
      visit[k]=1;
for(j=1;j<=N;j++)
     {
if(!visit[j]&&map[k][j].i!=inf&&dis[j]>=dis[k]+map[k][j].i)
         {
          dis[j]=dis[k]+map[k][j].i;
          P[j]=P[k]+map[k][j].j;

if(j==y)
         {
//printf("**:%d %d\n",dis[y],P[y]);
         C[l].a=dis[y];
         C[l++].b=P[y];
         }
         }
     }
   }
if(l>=2)
   {
   qsort(C,l,sizeof(C[0]),cmp);
   printf("%d %d\n",C[0].a,C[0].b);
  }
else
  printf("%d %d\n",dis[y],P[y]);
}


int main( )
{
//Debug();
 while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
 {
int i,j,k,a,b,c,d,start,end;
for(i=0;i<=N;i++)
for(j=0;j<=N;j++)
    map[i][j].i=map[j][i].i=map[i][j].j=map[j][i].j=inf;
for(i=0;i<M;i++)
  {
  scanf("%d%d%d%d",&a,&b,&c,&d);
if(map[a][b].i>=c)
  {
  map[a][b].i=map[b][a].i=c;
  map[a][b].j=map[b][a].j=d;
  }
 }
 scanf("%d%d",&start,&end);
 dij(start,end);
}
//system("pause");
return 0;
}