91 条题解
-
0
wizard1990 LV 3 @ 2008-08-24 10:33:13
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 72ms
floyd居然华丽的过了...... -
0
1次dijkstra就行
dist中包含弯道所用时间
answer := min(dist[i] + a[i, 1]);
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 72ms好题
首先求出每个点到1的距离和1到每个点的距离。然后求min(dis+dis[1,i]);
注意阴人点：边可重时应取最小。
-
0
fOrmkNight LV 3 @ 2008-08-20 21:40:59
这道题大家用C++的千万不要用cin cout。。。
用printf scanf!!!
害得我Floyd,Dijkstra都是TLE最后一个点。。。
一个百分点的正确率啊。。。。。。 -
0
tracy-henry LV 10 @ 2008-08-20 15:04:47
正版的usaco式阴人方法。
-
-1
var dist,time:array[0..201] of longint;
map:array[0..201,0..201] of longint;
i,ans,n,m,j,a,b,c:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procedure spfa;
var h,t,x:longint;
vis:array[0..201] of boolean;
q:array[0..201] of longint;
begin
fillchar(vis,sizeof(vis),false);
fillchar(q,sizeof(q),0);
h:=0;t:=1;q[1]:=1;vis[1]:=true;dist[1]:=time[1];
while h<>t do
begin
h:=h mod n+1;
x:=q[h];
vis[x]:=false;
for i:=1 to n do
if (map[x,i]<>maxlongint shr 1) and (dist[x]+map[x,i]+time[i]<dist[i]) then
begin
dist[i]:=dist[x]+map[x,i]+time[i];
if not(vis[i]) then
begin
t:=t mod n+1;
q[t]:=i;
vis[i]:=true;
end;
end;
end;
end;
begin
readln(n,m);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=maxlongint shr 1;
for i:=1 to n do readln(time[i]);
for i:=1 to m do
begin
readln(a,b,c);
map[a,b]:=min(map[a,b],c);
end;
for i:=1 to n do dist[i]:=maxlongint shr 1;
spfa;
ans:=maxlongint;
for i:=2 to n do ans:=min(ans,dist[i]+map[i,1]);
if ans>maxlongint shr 1 then writeln('-1') else writeln(ans);
end.
wizard1990
LV 3
@ 2008-08-24 10:33:13
