社区讨论
0是什么操作
P3371【模板】单源最短路径(弱化版)参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi6hduru
- 此快照首次捕获于
- 2025/11/20 04:54 4 个月前
- 此快照最后确认于
- 2025/11/20 04:54 4 个月前
CPP
var
dis,s,t,w,v,next,list,p:array[0..500001]of longint;
i,j,n,m,z,r,head,tail,ans,max,q:longint;
begin
read(n,m,z);
for i:=1 to m do
begin
read(s[i],t[i],w[i]);
next[i]:=list[s[i]];
list[s[i]]:=i;
end;
for i:=1 to n do
dis[i]:=maxlongint div 2;
tail:=1;
p[1]:=z;
dis[q]:=0;
v[z]:=1;
dis[1]:=0;
i:=1;
while head<tail do
begin
inc(head);
i:=list[p[head]];
while i>0 do
begin
if dis[s[i]]+w[i]<dis[t[i]] then
begin
dis[t[i]]:=dis[i]+w[i];
if v[t[i]]=0 then
begin
inc(tail);
v[t[i]]:=1;
p[tail]:=t[i];
end;
end;
i:=next[i];
end;
v[list[head]]:=0;
end;
for i:=1 to n do write(dis[i],' ');
end.
回复
共 2 条回复,欢迎继续交流。
正在加载回复...