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无数次

Posted by liyounan at 2011-03-05 11:30:24 on Problem 1847
program poj1847;
var
  x:array[1..200,1..200] of longint;
  f:array[1..200] of boolean;
  d:array[1..200] of longint;
  n,a,b,i,j,k,l,min:longint;
begin
  fillchar(f,sizeof(f),false);
  readln(n,a,b);
  for i:=1 to n do
    for j:=1 to n do
    begin
      if i=j then x[i,j]:=0
      else x[i,j]:=maxlongint;
    end;
  for i:=1 to n do
  begin
    read(k);
    for j:=1 to k do
    begin
      read(l);
      if j<>1 then x[i,l]:=1
      else x[i,l]:=0;
    end;
  end;
  f[a]:=true;
  for i:=1 to n do d[i]:=x[a,i];
  for i:=2 to n do
  begin
    min:=maxint;
    for j:=1 to n do
     if (not f[j])and(d[j]<min) then
     begin
       min:=d[j];
       k:=j;
     end;
    f[k]:=true;
    for j:=1 to n do
     if (not f[j])and(d[k]+x[k,j]<d[j])
       then d[j]:=d[k]+x[k,j];
  end;
  if d[b]=maxlongint then writeln(-1) else writeln(d[b]);
end.

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