记录编号 |
21551 |
评测结果 |
AAAAAAAAAA |
题目名称 |
奶牛派对 |
最终得分 |
100 |
用户昵称 |
ZhouZn1 |
是否通过 |
通过 |
代码语言 |
Pascal |
运行时间 |
0.136 s |
提交时间 |
2010-11-11 15:35:19 |
内存使用 |
7.75 MiB |
显示代码纯文本
program zzn;
var
i,j,n,m:longint;
dist:array[1..2,1..1000]of longint;
map:array[1..2,1..1000,1..1000]of longint;
x,a,b,t:longint;
procedure init;
begin
assign(input,'party.in');
reset(input);
assign(output,'party.out');
rewrite(output);
readln(n,m,x);
for i:=1 to n do
for j:=1 to n do if i<>j then
begin
map[1,i,j]:=100000;
map[2,i,j]:=100000;
end else
begin
map[1,i,j]:=0;
map[2,i,j]:=0;
end;
for i:=1 to m do
begin
readln(a,b,t);
map[1,a,b]:=t;
map[2,b,a]:=t;
end;
for i:=1 to n do
if i<>x then
begin
dist[1,i]:=map[1,x,i];
dist[2,i]:=map[2,x,i];
end;
dist[1,x]:=0;dist[2,x]:=0;
end;
procedure closef;
begin
close(input);
close(output);
end;
procedure djs(k:integer);
var
v:array[1..1000]of boolean;
min,p:longint;
begin
fillchar(v,sizeof(v),0);
v[x]:=true;
for i:=1 to n-1 do
begin
min:=maxlongint;
for j:=1 to n do
begin
if (dist[k,j]<min)and(not v[j]) then
begin
min:=dist[k,j];
p:=j;
end;
end;
v[p]:=true;
for j:=1 to n do if not(v[j])then
if dist[k,j]>dist[k,p]+map[k,p,j] then
dist[k,j]:=dist[k,p]+map[k,p,j];
end;
end;
procedure main;
var
ans:longint;
begin
djs(1);
djs(2);
ans:=-maxlongint;
for i:=1 to n do
if dist[1,i]+dist[2,i]>ans then ans:=dist[1,i]+dist[2,i];
writeln(ans);
end;
begin
init;
main;
closef;
end.