记录编号 |
8114 |
评测结果 |
AAAAAAAA |
题目名称 |
旅行计划 |
最终得分 |
100 |
用户昵称 |
王瑞祥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.