【题意】
给定一个单词库,有一个起始单词,从这个单词出发,每次在任意位置加一个任意字母变成另外一个单词,问最多能加几次,输出最长单词
【输入】
第一行n 起始单词
接下来n行每行一个单词
【输出】
最长单词,数据保证唯一
按长度排下序,试试长度相差1的两个点是否能转换,可以转换连一条边,然后做spfa,输出距离最远的点
program poj2138; var ans,tot,st,n,i,j,k:longint; fin:array [0..81] of longint; root,dis:array [0..1001] of longint; dl:array [0..2001] of longint; next,point:array [0..200001] of longint; str:array [0..1001] of string; sta:string; space:char; procedure swap (var a,b:string);inline; var i:string; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=length(str[(s+e) div 2]); while i<=j do begin while length(str[i])<k do inc(i); while length(str[j])>k do dec(j); if i>j then break; swap(str[i],str[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; procedure connect (u,v:longint);inline; begin inc(tot); point[tot]:=v; next[tot]:=root[u]; root[u]:=tot; end; function ok (a,b:longint):boolean; var i:longint; begin for i:=1 to length(str[b]) do if str[a]=copy(str[b],1,i-1)+copy(str[b],i+1,length(str[b])-i) then exit(true); exit(false); end; begin readln(n,space,sta); for i:=1 to n do readln(str[i]); qsort(1,n); for st:=1 to n do if str[st]=sta then break; i:=1; while i<=n do begin k:=length(str[i]); while length(str[i])=k do inc(i); fin[k]:=i-1; end; for i:=1 to n do for j:=fin[length(str[i])]+1 to fin[length(str[i])+1] do if ok(i,j) then connect(i,j); fillchar(dis,sizeof(dis),63); tot:=1; i:=1; dl[1]:=st; dis[st]:=1; ans:=st; while i<=tot do begin k:=root[dl[i]]; while k<>0 do begin if dis[point[k]]>dis[dl[i]]+1 then begin dis[point[k]]:=dis[dl[i]]+1; if dis[point[k]]>dis[ans] then ans:=point[k]; inc(tot); dl[tot]:=point[k]; end; k:=next[k]; end; inc(i); end; writeln(str[ans]); end.