首页 > 代码库 > CODEVS1079 回家 (最短路)

CODEVS1079 回家 (最短路)

  真是语死早,题目看了两遍才看懂。

  按照题目要求建边,从‘Z‘开始跑最短路即可。

 

Program CODEVS1079;var a:array[0..1000,0..1000] of longint;    d:array[0..1000] of longint;    pd:array[0..1000] of boolean;    flag:array[0..1000] of boolean;    b:array[0..10000] of longint;    ch,space,ch2,ans:char;    i,j,m,x,min:longint;procedure spfa(s:longint);var i,j,l,r,u,v:longint;begin  fillchar(pd,sizeof(pd),false);  fillchar(b,sizeof(b),0);  fillchar(d,sizeof(d),$7f);  l:=1; r:=1; pd[s]:=true; b[l]:=s; d[s]:=0;  while l<=r do    begin      u:=b[l];      for v:=ord(A) to ord(z) do        if (a[u,v]<10000) and (d[u]+a[u,v]<d[v]) then          begin            d[v]:=d[u]+a[u,v];            if not pd[v] then              begin                inc(r);                b[r]:=v;                pd[v]:=true;              end;          end;      inc(l);      pd[u]:=false;    end;end;begin  fillchar(flag,sizeof(flag),false);  fillchar(a,sizeof(a),$7f);  readln(m);  for i:=1 to m do    begin      readln(ch,space,ch2,space,x);      if x>a[ord(ch),ord(ch2)] then continue;      a[ord(ch),ord(ch2)]:=x;      a[ord(ch2),ord(ch)]:=x;      flag[ord(ch)]:=true;      flag[ord(ch2)]:=true;    end;    min:=maxlongint;  spfa(ord(Z));  for i:=ord(A) to ord(Y) do    if flag[i] then      if d[i]<min then        begin          ans:=chr(i);          min:=d[i];        end;  writeln(ans, ,min);end.

 

CODEVS1079 回家 (最短路)