记录编号 8114 评测结果 AAAAAAAA
题目名称 旅行计划 最终得分 100
用户昵称 Gravatar王瑞祥K 是否通过 通过
代码语言 Pascal 运行时间 0.028 s
提交时间 2008-11-12 21:58:06 内存使用 0.17 MiB
显示代码纯文本
program djs(input,output);
const
 maxnum=3000000;
var
 ga:array[0..100,0..100]of longint;
 dist:array[0..100]of longint;
 path:array[0..100,0..100]of integer;
 s:array[0..100]of boolean;
 n,m,v:integer;
procedure ini;
var i,j,sta,fin,leng:longint;
begin
 assign(input,'djs.in');assign(output,'djs.out');
 reset(input);rewrite(output);
 readln(n,m,v);
 for i:=0 to n do
  for j:=0 to n do
   ga[i,j]:=maxnum;
 for i:=1 to m do begin
  readln(sta,fin,leng);
  ga[sta,fin]:=leng;
 end;
end;
procedure dijkstra;
var i,j,k,m,w:longint;
begin
 for i:=0 to n-1 do begin
  if i<>v then s[i]:=false else s[i]:=true;
  dist[i]:=ga[v,i];
  if dist[i]<maxnum then begin
   path[i,0]:=2;
   path[i,1]:=v;
   path[i,2]:=i;
  end else path[i,0]:=0;
 end;
 for j:=0 to n-2 do begin
  w:=maxnum; m:=v;
  for i:=0 to n-1 do
   if not s[i] and (dist[i]<w) then begin m:=i; w:=dist[i]; end;
  if m<>v then s[m]:=true else exit;
  for i:=0 to n-1 do
   if not s[i] and(dist[m]+ga[m,i]<dist[i]) then begin
    dist[i]:=dist[m]+ga[m,i];
    for k:=1 to path[m,0] do path[i,k]:=path[m,k];
    path[i,0]:=k+1; path[i,k+1]:=i;
   end;
 end;
end;
procedure print;
var i,j:integer;
begin
 for i:=0 to n-1 do begin
  writeln(i,':');
  if path[i,0]=0 then writeln('no')
  else begin
   write('path:');
   for j:=1 to path[i,0] do write(path[i,j],' ');
   writeln;
   writeln('cost:',dist[i]);
  end;
 end;
end;
begin
 ini;
 dijkstra;
 print;
 close(input);close(output);
end.