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

啊啊啊啊,为什么啊,Dijkstra无限WA啊,Floyd一次AC,谁帮我看下Dj的算法错在哪里啊

Posted by 1104272319 at 2016-08-09 20:24:42 on Problem 1847
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 99999999;
const int maxn = 220;

int e[maxn][maxn],dis[maxn],i,j,book[maxn],minn,tmp;
int u,v;
int n,start,eend,m,t1,t2,t3;




int main()
{
//   freopen("in.txt","r",stdin);
   while(scanf("%d %d %d",&n,&start,&eend)!=EOF){

   for(i=1;i<=n;i++){
            dis[i]=INF;
        for(j=1;j<=n;j++)
        if(i==j)
         e[i][j]=0;
         else
            e[i][j]=INF;
}

   for(i=1;i<=n;i++){
     scanf("%d",&m);

      for(j=1;j<=m;j++){
        scanf("%d",&t1);
        if(j==1)
            e[i][t1]=0;
            else
            e[i][t1]=1;
      }
    }


 for(i=1;i<=n;i++)
    dis[i]=e[start][i];
    dis[start]=0;

 memset(book,0,sizeof(book));
 book[start]=1;



 for(i=1;i<=n;i++){
    minn=INF;
    for(j=1;j<=n;j++){
        if(book[j]==0&&dis[j]<minn){
            minn=dis[j];
            u = j;
        }
    }

    book[u]=1;
    for(v=1;v<=n;v++){
        if(e[u][v]<INF){
            if(dis[v]>dis[u]+e[u][v])
                dis[v]=dis[u]+e[u][v];
        }
    }
 }

   if(dis[eend]<INF)
      printf("%d\n",dis[eend]);
   else
       cout<<"-1"<<endl;
   }
 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