比赛 |
不平凡的世界 |
评测结果 |
AAAWWAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
80 |
用户昵称 |
Derrick_M |
运行时间 |
0.805 s |
代码语言 |
Pascal |
内存使用 |
4.10 MiB |
提交时间 |
2015-11-05 09:10:42 |
显示代码纯文本
program P2095;
type
roads=record
toit,next,val:longint;
end;
var
road:array[1..200010] of roads;
min1,min2,minn,list,a:array[1..100010] of longint;
leaf,flag:array[1..100010] of boolean;
max0,ans,n,m,i,u,v,w,root,cnt:longint;
procedure add(u,v,w:longint);
begin
inc(cnt);
road[cnt].toit:=v;
road[cnt].next:=list[u];
road[cnt].val:=w;
list[u]:=cnt;
inc(a[v]);
end;
procedure dfs(u:longint);
var
v,w:longint;
begin
flag[u]:=true;
if leaf[u] then
begin
min1[u]:=0;
exit;
end;
w:=list[u];
while w<>0 do
begin
v:=road[w].toit;
if not flag[v] then
begin
dfs(v);
if min1[u]>min1[v]+road[w].val then
begin
min2[u]:=min1[u];
min1[u]:=min1[v]+road[w].val;
minn[u]:=v;
end
else
if min2[u]>min1[v]+road[w].val then
min2[u]:=min1[v]+road[w].val;
end;
w:=road[w].next;
end;
end;
function getmin(u,v:longint):longint;
begin
if u<v then exit(u)
else exit(v);
end;
procedure work(u,v0:longint);
var
v,w,min:longint;
begin
flag[u]:=true;
w:=list[u];
if leaf[u] then
begin
if v0>ans then ans:=v0;
exit;
end;
while w<>0 do
begin
v:=road[w].toit;
if not flag[v] then
begin
if minn[u]=v then min:=min2[u]
else min:=min1[u];
work(v,getmin(min,v0)+road[w].val);
end;
w:=road[w].next;
end;
end;
begin
assign(input,'firelead.in');assign(output,'firelead.out');
reset(input);rewrite(output);
readln(m);
n:=m+1;
for i:=1 to m do
begin
readln(u,v,w);
add(u,v,w);
add(v,u,w);
end;
fillchar(leaf,sizeof(leaf),false);
for i:=1 to n do
if a[i]=1 then leaf[i]:=true
else root:=i;
fillchar(min1,sizeof(min1),$6F);
fillchar(min2,sizeof(min2),$6F);
fillchar(max0,sizeof(max0),$6F);
dfs(root);
fillchar(flag,sizeof(flag),false);
ans:=0;
work(root,max0);
writeln(ans/2:0:1);
close(input);close(output);
end.