98 条题解
-
0
小岛 LV 10 @ 2009-04-03 12:15:22
校本课老师给我们放了越狱...#24
-
0
var
a:array[0..2000,0..2000] of longint;
d:array[1..2000] of longint;
v:array[1..2000] of boolean;
max,n,k,x,y,i,j:longint;
function min(c,d:longint):longint;
begin
if c>d then
exit(d)
else exit(c);
end;
begin
assign(input,'break.in');
reset(input);
assign(output,'break.ans');
rewrite(output);
read(n);
read(x,y,a[x,y]);
while x0 do
read(x,y,a[x,y]);
for i:=2 to n do
d[i]:=a[1,i];
for i:=2 to n do
begin
max:=0;
for j:=1 to n do
if (d[j]>max)and(not v[j]) then
begin
max:=d[j];
k:=j;
end;
v[k]:=true;
for j:=1 to n do
if (not v[j])and(min(a[k,j],d[k])>d[j]) then
d[j]:=min(a[k,j],d[k]);
end;
for i:=2 to n do
writeln(d[i]);
close(input);
close(output);
end.
我是菜鸟 -
0
const
maxn=1000000;
var
map:array[0..2000,0..2000]of longint;
dist,pre:array[0..2000]of longint;
v:array[0..2000]of boolean;
n,a,i,j,b,c,min,k:longint;
beginreadln(n);
readln(a,b,c);
for i:=1 to n do
for j:=1 to n do
map:=-maxn;
map[a,b]:=c;
while (a0) or (b0) or (c0) do
begin
readln(a,b,c);
map[a,b]:=c;
end;
pre[1]:=0;
v[1]:=true;
for i:=2 to n do
begin
dist[i]:=map[1,i];
pre[i]:=1;
end;
for i:=1 to n do
begin
min:=-maxn;
for j:=1 to n do
if (dist[j]>min) and (not v[j]) then
begin
min:=dist[j];
k:=j;
end;
v[k]:=true;
for j:=1 to n do
if (map[k,j]>dist[j]) and (not v[j]) then
begin
dist[j]:=map[k,j];
pre[j]:=k;
end;
end;
for i:=2 to n do
begin
if dist[i]-maxn then
begin
min:=maxn;
k:=i;
while k1 do
begin
if map[pre[k],k] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 41ms
├ 测试数据 05：答案正确... 25ms
├ 测试数据 06：答案正确... 56ms
├ 测试数据 07：答案正确... 41ms
├ 测试数据 08：答案正确... 41ms
├ 测试数据 09：答案正确... 56ms
├ 测试数据 10：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：301msdijkstra速度还可以。最小边最大值问题。
-
0
为什么0分啊
const
maxn=2000;
var
a:array[1..maxn,1..maxn]of longint;
dis:array[1..maxn]of longint;
can:array[1..maxn]of boolean;
i,j,k,p,n,min:longint;
function mi(x,y:longint):longint;
begin
if xmin) then
begin
min:=dis[j];k:=j;
end;
can[k]:=false;
for j:=2 to n do
if can[j]and(mi(dis[k],a[k,j])>dis[j])and(a[k,j]0)then
dis[j]:=mi(dis[k],a[k,j]);
end;
for i:=2 to n do
writeln(dis[i]);
end. -
0
fammiebright LV 9 @ 2008-10-29 09:28:57
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 9ms
├ 测试数据 06：答案正确... 9ms
├ 测试数据 07：答案正确... 9ms
├ 测试数据 08：答案正确... 9ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：54ms如果把longint打成integer就0分了。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
也是spfa，用邻接表就会快一点 -
0
181818181818 LV 10 @ 2008-09-04 22:03:37
借用DIJKSTRA的思想干掉。
longint打成integer，郁闷…… -
0
这不是代码。。。
program p1391;
const
maxn=2000;
var
r,e:array[1..maxn,1..maxn] of longint;
tot,d:array[1..maxn] of longint;
v:array[1..maxn] of boolean;
n,m,i,j:longint;
function min(a,b:longint):longint; begin
min:=a; if min>b then min:=b;
end;
function max(a,b:longint):longint; begin
max:=a; if max -
0
lmjgood520 LV 9 @ 2008-08-22 21:07:36
好象没人用DIJSKTRA
其实用DIJSKTRA就行了
初始化dis[j]为g[1,j];
每次选出最大dis[k]
然后看是否能将其他的dis[j] 更新;
能更新的情况有
首先都要满足k到j有边(g[k,j]0);
然后:(1):当前没有路通向j(dis[j]=0);
(2):当前的dis[j] -
0
LittleRock LV 8 @ 2008-08-08 15:38:17
不要怪我
SPFA的头尾指针都mod去了
结果错了
- -
囧死了
小岛
LV 10
@ 2009-04-03 12:15:22
