大师作文网pascal tyvj1083问题……（广搜）
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/10 22:49:48
pascal tyvj1083问题……（广搜）
From Admin
☆分糖果
描述 Description
童年的我们,将和朋友分享美好的事物作为自己的快乐.这天,C小朋友得到了Plenty of candies,将要把这些糖果分给要好的朋友们.已知糖果从一个人传给另一个人需要1 秒的时间,同一个小朋友不会重复接受糖果.由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果.由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发.每个小朋友从接受糖果到吃完糖果需要m秒的时间.那么,如果第一秒C小朋友开始发糖,第多少秒所有小朋友都吃完了糖呢?
输入格式 Input Format
第一行为三个数n、p、c,为小朋友数、关系数和C小朋友的编号.
第二行为一个数m,表示小朋友吃糖的时间.
下面p行每行两个整数,表示某两个小朋友在彼此身旁
输出格式 Output Format
一个数,为所有小朋友都吃完了糖的时间
样例输入 Sample Input [复制数据]
4 3 1
2
1 2
2 3
1 4
样例输出 Sample Output [复制数据]
5
From Admin
☆分糖果
描述 Description
童年的我们,将和朋友分享美好的事物作为自己的快乐.这天,C小朋友得到了Plenty of candies,将要把这些糖果分给要好的朋友们.已知糖果从一个人传给另一个人需要1 秒的时间,同一个小朋友不会重复接受糖果.由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果.由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发.每个小朋友从接受糖果到吃完糖果需要m秒的时间.那么,如果第一秒C小朋友开始发糖,第多少秒所有小朋友都吃完了糖呢?
输入格式 Input Format
第一行为三个数n、p、c,为小朋友数、关系数和C小朋友的编号.
第二行为一个数m,表示小朋友吃糖的时间.
下面p行每行两个整数,表示某两个小朋友在彼此身旁
输出格式 Output Format
一个数,为所有小朋友都吃完了糖的时间
样例输入 Sample Input [复制数据]
4 3 1
2
1 2
2 3
1 4
样例输出 Sample Output [复制数据]
5
program p1083;
type node=^tnode;
tnode=record
b,c:longint;
next:node;
end;
var ans,n,m,p,c:longint;
g:array[1..100000]of node;
d:array[1..100000]of longint;
v:array[1..100000]of boolean;
dist:array[1..100000]of longint;
procedure init;
var i,j,x,y:longint; q:node;
begin
readln(n,p,c);
readln(m);
for i:=1 to n do g[i]:=nil;
for i:=1 to p do
begin
readln(x,y);
new(q); q^.b:=y; q^.c:=1; q^.next:=g[x]; g[x]:=q;
new(q); q^.b:=x; q^.c:=1; q^.next:=g[y]; g[y]:=q;
end;
end;
procedure spfa;
var head,tail,now,i,j,k:longint; q:node;
begin
for i:=1 to n do v[i]:=false;
for i:=1 to n do dist[i]:=maxlongint;
head:=0; tail:=1; d[1]:=1; v[1]:=true; dist[1]:=0;
while headtail do
begin
head:=head mod 100000+1;
now:=d[head];
q:=g[now];
while qnil do
begin
if dist[q^.b]>dist[now]+q^.c then
begin
dist[q^.b]:=dist[now]+q^.c;
if v[q^.b]=false then
begin
tail:=tail mod 100000+1;
d[tail]:=q^.b;
v[q^.b]:=true;
end;
end;
q:=q^.next;
end;
v[now]:=false;
end;
ans:=0;
for i:=2 to n do
if dist[i]>ans then ans:=dist[i];
ans:=ans+1+m;
writeln(ans);
end;
begin
init;
spfa;
end.
type node=^tnode;
tnode=record
b,c:longint;
next:node;
end;
var ans,n,m,p,c:longint;
g:array[1..100000]of node;
d:array[1..100000]of longint;
v:array[1..100000]of boolean;
dist:array[1..100000]of longint;
procedure init;
var i,j,x,y:longint; q:node;
begin
readln(n,p,c);
readln(m);
for i:=1 to n do g[i]:=nil;
for i:=1 to p do
begin
readln(x,y);
new(q); q^.b:=y; q^.c:=1; q^.next:=g[x]; g[x]:=q;
new(q); q^.b:=x; q^.c:=1; q^.next:=g[y]; g[y]:=q;
end;
end;
procedure spfa;
var head,tail,now,i,j,k:longint; q:node;
begin
for i:=1 to n do v[i]:=false;
for i:=1 to n do dist[i]:=maxlongint;
head:=0; tail:=1; d[1]:=1; v[1]:=true; dist[1]:=0;
while headtail do
begin
head:=head mod 100000+1;
now:=d[head];
q:=g[now];
while qnil do
begin
if dist[q^.b]>dist[now]+q^.c then
begin
dist[q^.b]:=dist[now]+q^.c;
if v[q^.b]=false then
begin
tail:=tail mod 100000+1;
d[tail]:=q^.b;
v[q^.b]:=true;
end;
end;
q:=q^.next;
end;
v[now]:=false;
end;
ans:=0;
for i:=2 to n do
if dist[i]>ans then ans:=dist[i];
ans:=ans+1+m;
writeln(ans);
end;
begin
init;
spfa;
end.