首页 > 代码库 > 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 回家 (最短路)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。