集训队作业_ural1314解题报告.pdfVIP

1314 Chase in Subway 解题报告 题意简述: 给定一无向图和一条路径,求到起点的某一条最短路包含该路径的所有点. 分析: 设路径的终点为 t,两点间距离为dis(I,j) 对于某一点 i,假设路径不包含在任一最短路中, 则必定存在路径上一点p,使得 dis(i,t)+dis(t,p)dis(I,p).于是, 分别可以对每个点进行 , 2 判断是否满足要求.复杂度为O(N ) 实现: 存图用临接表.单位耗散量问题可以考虑用广搜.到t 的距离预先处理好,到I 点的距离 临时求,使得空间降到一维,而时效不变.可能的点 为 1~32767,导致每次初始化的代价偏 高.但实质上用到的点不会超过 50*50=2500 个,所以可以把他们存下来,只初始化这些点即可. 注意: 路径只有一个点; 图为一个环. 实际上,当找到路径上除 t 外一点就可进行判断了. 另 外,本题也许存 性的算法. 程序: type link=^node; node=record v:integer; next:link; end; var map:array[1..32767]of link; visit:array[1..32767]of boolean; mark,dis:array[1..32767]of integer; stack,used:array[1..3000]of integer; s,ls,ld:integer; procedure add(i,j:integer); var p:link; begin new(p); p^.v:=j; p^.next:=map[i]; map[i]:=p; new(p); p^.v:=i; p^.next:=map[j]; map[j]:=p; end; procedure readin; var n,i,j,k:integer; a:array[1..50]of integer; begin assign(input,input.in); reset(input); readln(n); for i:=1 to 32767 do map[i]:=nil; for i:=1 to n do begin read(k); for j:=1 to k do read(a[j]); readln; for j:=1 to k-1 do add(a[j],a[j+1]); end; read(k); fillchar(visit,sizeof(visit),0); for i:=1 to k-1 do begin read(j); visit[j]:=true; end; readln(s); ld:=0; for i:=1 to 32767 do if map[i]nil then begin inc(ld); used[ld]:=i; end; end; procedure prepare; var i,head:integer; p:link; begin for i:=1 to ld do dis[used[i]]:=maxint; head:=1; ls:=1; stack[1]:=s; dis[s]:=0; while head=ls do begin p:=map[stack[head]]; i:=stack[head]; while pnil do begin if dis[i]+1dis[p^.v] then begin