const x='v389.in';
y='v389.out';
var map:array[1..250,1..250]of longint;
dis:array[1..250,1..250]of longint;
i,j,k,m,n,p,q,r,mi:longint;
function min(x,y:longint):longint;
begin
if x<y
then min:=x
else min:=y;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(p,q,r);
map[p,q]:=r;
map[q,p]:=r;
dis[p,q]:=r;
dis[q,p]:=r;
end;
mi:=maxint;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
if map[i,k]*map[k,j]*dis[i,j]<>0
then mi:=min(mi,map[i,k]+map[k,j]+dis[i,j]);
for i:=1 to n do
for j:=1 to n do
if dis[i,k]*dis[k,j]<>0
then dis[i,j]:=min(dis[i,j],dis[i,k]+dis[k,j]);
end;
if mi<maxint
then writeln(mi)
else writeln('He will never come back.');
end.
状态: Unaccepted
测评机： Xeond[6]
得分： 90分
提交日期： 2010-10-23 1:15:00
有效耗时： 1359毫秒
测试结果1: 通过本测试点|有效耗时156ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时156ms
测试结果5: 通过本测试点|有效耗时188ms
测试结果6: 通过本测试点|有效耗时187ms
测试结果7: 通过本测试点|有效耗时172ms
测试结果8: 测试结果错误.错误结果为:139
正确结果应为:122
测试结果9: 通过本测试点|有效耗时188ms
测试结果10: 通过本测试点|有效耗时218ms
yiyu9261wsx我看你当时做的时候开始跟我错的一样的，
不知道你后来是怎么AC的
如果不是加if ans=139 then ans:=122;的话
能不能跟我说下你是怎么改的？
program heart_dijkstra;
type color=(white,gray,black);
const maxn=250;
var adj:Array[0..maxn,0..maxn]of dword;
path,path2:array[0..maxn]of dword;
f:array[0..maxn]of color;
i,j,k,m,n,w,a,b:integer;
bre:longint;
ans,step:dword;
function dijkstra(st,ed:integer;all:boolean):dword;
var i,j,k:integer;
s,min:dword;
begin
for i:=1 to n do f[i]:=white;
filldword(path,sizeof(path) shr 2,maxlongint-1);
f[st]:=gray;
path[st]:=0;
while true do
begin
k:=0;
min:=maxlongint;
for i:=1 to n do
if (f[i]=gray)and(path[i]<min)then
begin
k:=i;
min:=path[i];
end;
f[k]:=black;
if (k=ed)and(not all) then break;
if k=0 then break;
for i:=1 to n do
begin
if f[i]=black then continue;
s:=path[k]+adj[k,i];
if s<path[i] then
begin
path[i]:=s;
f[i]:=gray;
end;
end;
end;
exit(path[ed]);
end;
{main}
begin
readln(n,m);
ans:=maxlongint;
for i:=1 to n do
for j:=1 to n do
adj[i,j]:=maxint;
for i:=1 to m do
begin
readln(a,b,w);
adj[a,b]:=w;
adj[b,a]:=w;
end;
for i:=1 to n do
begin
dijkstra(i,n,true);
for j:=1 to n do
path2[j]:=path[j];
for j:=1 to n do
begin
if adj[j,i]=maxint then continue;
if path2[j]*2>=ans then continue;
bre:=adj[j,i];
adj[j,i]:=maxint;
adj[i,j]:=maxint;
step:=dijkstra(j,i,false);
adj[j,i]:=bre;
adj[i,j]:=bre;
if step+bre<ans then
ans:=step+bre;
end;
end;
if ans>=maxint then
begin
writeln('He will never come back.');
halt;
end;
writeln(ans);
end.