首页 > 代码库 > 黑猫派对
黑猫派对
【问题描述】
黑猫搬家到了狂气之城---千叶，在凶介的鼓励下，她交到了很多很多好朋友，这天，大家决定聚到一起，到某个人家里去玩，黑猫的朋友（包括她自己）有 N 个人，他们决定一起到被编号为 X 的朋友家里去，大家都住在不同的地方，被很多条单向道路连接着，大家都会选择最短路径到达目的地和回家，现在黑猫手上拿着一份地图，标记着所有人的位置以及道路长度，她想知道前去聚会的人中，到达目的地之后又回家要走的距离最长的那个人要走多长的距离？
【输入】
第一行有三个整数 N，M，X。
第2~m+1 行：a,b,c，表示有一条从 a到b的路，长度为c(<=1000000)。
【输出】
一个数ans，距离X最长的那个人要走多长的距离。
【输入输出样例】
party.in | party.out |
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
| 10
|
【数据范围限制】
30%的数据，满足 N<=1000，M<=100000
100%的数据，满足 N<=10000，M<=1000000，1<=X<=N 。
有可能有通往自己家的单向道路（自环），和多条通往一个地方的单向道路（重边）
题目解析：
从题目可以看出需要做两次单源最短路径，一次正向，一次反向（即将所有的边反过来即可）。
dij,O(N2)明显超时。
spfa,O(Ke)，在平均情况下K是常数，应该没问题。
此题注意数组的大小，要开足够大。
//注意数组空间一定要开的足够大，这是spfa错误的主要原因。const maxn=210000; maxm=2100000; fin=‘party.in‘; fout=‘party.out‘;var n,m,tot,tot2,i,start:longint; q,list,list2,d,d2:array[1..maxn] of longint; //list存储当前边的指针,d存储各点到源点的最短路 next,next2,toit,toit2,cost2,cost:array[1..maxm] of longint;//next存储当前边指向前一条边的位置，toit表示当前边的出点，cost表示当前边的边权 f:array[1..maxn] of boolean; head,tail:longint; procedure makelist(x,y,w:longint);////数组模拟链表的添边的方法 begin inc(tot);////边的数目 toit[tot]:=y;//当前边的出点顶点标号 cost[tot]:=w;//当前边的权值? next[tot]:=list[x];////当前边指向前一条边的位置，如果当前边是顶点x的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0 list[x]:=tot;//从入点x引出的边的编号存储给lsit[x] end; procedure makelist2(x,y,w:longint);////数组模拟链表的添边的方法 begin inc(tot2);////边的数目 toit2[tot2]:=y;//当前边的出点顶点标号 cost2[tot2]:=w;//当前边的权值? next2[tot2]:=list2[x];////当前边指向前一条边的位置，如果当前边是顶点x的读入的第一条边，则它指向前面第0条边，表示next[tot]:=0 list2[x]:=tot2;//从入点x引出的边的编号存储给lsit[x] end; procedure init; var i,j,x,y,w:longint; begin assign(input,fin);reset(input); tot:=0; tot2:=0; fillchar(f,sizeof(f),true); fillchar(next,sizeof(next),0); fillchar(cost,sizeof(cost),0); fillchar(toit,sizeof(toit),0); readln(n,m,start); for i:=1 to m do begin readln(x,y,w); makelist(x,y,w); makelist2(y,x,w) end; end; procedure spfa(start:longint); var i,x,y,t:longint; begin for i:=1 to n do d[i]:=maxint; d[start]:=0; head:=0;tail:=1; q[1]:=start;f[start]:=false; //源点start入队 while head<tail do begin inc(head); //队首元素出队，t存储当前x顶点的边的编号 x:=q[head]; t:=list[x]; //t存储当前x顶点的边的编号 f[x]:=true; while t<>0 do //处理x的所有边 begin y:=toit[t]; //y存储第t条边的另一个顶点 if d[x]+cost[t]<d[y] then //松驰操作 begin d[y]:=d[x]+cost[t]; if f[y] then begin inc(tail);q[tail]:=y;f[y]:=false;end;//入队 end; t:=next[t];//处理顶点x的下一条边 end; end; end; procedure spfa2(start:longint); var i,x,y,t:longint; begin fillchar(f,sizeof(f),true); for i:=1 to n do d2[i]:=maxint; d2[start]:=0; head:=0;tail:=1; q[1]:=start;f[start]:=false; //源点start入队 while head<tail do begin inc(head); //队首元素出队，t存储当前x顶点的边的编号 x:=q[head]; t:=list2[x]; //t存储当前x顶点的边的编号 f[x]:=true; while t<>0 do //处理x的所有边 begin y:=toit2[t]; //y存储第t条边的另一个顶点 if d2[x]+cost2[t]<d2[y] then //松驰操作 begin d2[y]:=d2[x]+cost2[t]; if f[y] then begin inc(tail);q[tail]:=y;f[y]:=false;end;//入队 end; t:=next2[t];//处理顶点x的下一条边 end; end; end; procedure print; var i,max:longint; begin assign(output,fout);rewrite(output); max:=-1; for i:=1 to n do if max<d[i]+d2[i] then max:=d[i]+d2[i]; writeln(max); close(output); end;begin init; spfa(start); spfa2(start); print;end.
黑猫派对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。