2100穿越封锁线(2012复赛模拟)

第一题: 穿越封锁线（cross.pas/c/cpp）

题目描述：

保卫钩鱼岛是我们每个公民的责任。对于窃取情报和破译密码，Feli 简直就是天才！在抗日作战中，Feli 已经多次成功的窃取日伪军的重要情报，为我军获取了大量作战取胜的关键筹码。

近日，将要进行保卫钩鱼岛战，Feli 又一次成功破译了对方的秘密电报。电报的内容为： 明天凌晨2：00，所有部队集中埋伏剿灭土八路3721整编军，天皇万福，保佑这次偷袭成功！

Feli 知道我军3721整编军是我军一支重点培养的生力军，如果在这次行动中遭受损失，那对我军将是一个十分严重的实力打击。这么重要的消息，必须赶紧传达到指挥步！由于抗战期间交通十分落后，Feli 只好委托Lucky 连夜将该消息送达总部。接到委托，Lucky 立即启程。

从情报站到指挥部之间有许多错综交叉的道路，道路和道路的交叉处都有地方可以供Lucky 躲藏。由于这里是交通要道，敌人也对这个地带十分关注：他们会时不时对在某些道路上派人巡逻。虽然Lucky 可以用精准的枪法将他们干掉，但是现在身负重任，不能打草惊蛇，所以必须避开他们。这意味着，如果某条道路有人巡逻，那么Lucky 将无法穿过。时间紧迫，Lucky 必须尽快到达总部。现在Lucky 再次向你求助，他应该如何行走才能用最短的时间到达指挥部。

说明：在每个交叉路口，Lucky 都能选择躲藏和行走。敌人的巡逻是周期循环的，他们总是以分钟为单位巡逻某条道路，在该分钟过去后离开。针对每条道路，我们假设Lucky 总是刚好用1分钟时间走完。

针对下列数据：

V={1,2,3,4,5}; E={(1,2),(2,3),(3,4),(2,4),(4,5),(1,3),(3,5)}

结点1为情报站，5为指挥部，其余为交叉路口。

周期为4分钟。

每个周期的第1分钟有巡逻的边为{(1,2),(2,4),(4,5)}

每个周期的第2分钟有巡逻的边为{(1,3),(2,3),(3,5)}

每个周期的第3分钟有巡逻的边为{(3,4),(4,5)}

每个周期的第4分钟没有巡逻边。

这样，Lucky 可以在第一分钟走边(1,3)，第二分钟躲藏，第3分钟走边(3,5)，消耗3分钟，时间最短。

数据说明：

每组输入数据第一行有2个整数n 和m （1≤n ≤100; 1≤m ≤500），代表地图有n 个结点m 条边。1号结总是代表情报站，n 号结点总是代表指挥部。

接下去m 行是对地图的描述，每行有2个小于n 的整数，分别代表一条边两端的结点编号。（如果边被重复描述，仍表示只有一条边）。

再接下去一行有一个整数k （0≤k ≤10）代表周期长度。

后来的数据都是对周期巡逻边的描述，每行有2个整数，表示被关注的边。0 0则表示对周期中某一分钟的巡逻边描述结束。数据保证在该段恰存在k 个0 0。

输出数据仅有一行，如果Lucky 可以到达指挥部，则输出到达指挥部的最短时间。如果不能到达则输出“No solution.”

样例输入(cross.in)：

样例输出(cross.out)：

解法：

把周期上的每个点分编K 个图，（如果K=0，则用原始图就可以）

然后，按time 进行广搜，进行时就按上面说的图走，当第n 个点找到了，就输出time 。 如果某个点连续K 个时间点都找不到续点，就不用再用这个点找。

标程1：

var t,n:integer;

got:array [1..100] of boolean;

map:array [0..9,1..100,1..100] of boolean;

procedure init;

var m,i,j,k:integer;

begin

fillchar(map,sizeof(map),0);

fillchar(got,sizeof(got),0);

readln(n,m);

for i:=1 to m do begin

readln(j,k);

map[0,j,k]:=true; map[0,k,j]:=true;

end;

readln(t);

for i:=1 to t-1 do

for j:=1 to n do

for k:=1 to n do map[i,j,k]:=map[0,j,k];

for i:=1 to t-1 do begin

readln(j,k);

if not((j=0)and(k=0)) then repeat

map[i,j,k]:=false; map[i,k,j]:=false;

readln(j,k)

until (j=0)and(k=0);

if t>0 then begin

readln(j,k);

if not((j=0)and(k=0)) then repeat

map[0,j,k]:=false; map[0,k,j]:=false;

readln(j,k)

until (j=0) and (k=0);

end;

end;

procedure print(a:longint);

begin

if a=-1 then writeln('No solution.') else writeln(a);

halt;

end;

function ct(p:integer):integer;

begin

if t=0 then exit(0) else exit(p mod t);

end;

procedure calc;

var i,j,p,head,tail,flag,time:integer;

q:array [1..100,1..2] of integer;

begin

fillchar(q,sizeof(q),0);

got[1]:=true; q[1,1]:=1; q[1,2]:=0; head:=1; tail:=1; time:=0; repeat

flag:=tail; inc(time); p:=ct(time);

for i:=head to tail do

for j:=1 to n do

if (map[p,q[i,1],j]) and (not got[j]) then begin

inc(flag);

q[flag,1]:=j; q[flag,2]:=p;

got[j]:=true;

end;

while (q[head,2]=p)and(head

if got[n] then print(time);

until tail

print(-1);

end;

begin

calc;

end.

标程2：

type qq=record

x,y,z:longint;

end;

var a,n,m,t,i,j:longint;

q:array[1..1050] of qq;

w:array[1..100,1..100] of boolean;

e,ch:array[0..10,1..100,1..100] of boolean;

begin

readln(n,m);

for a:=1 to n do w[a,a]:=true;

for a:=1 to m do begin

readln(i,j);

w[i,j]:=true; w[j,i]:=true;

end;

readln(t);

for a:=1 to t do begin

readln(i,j);

while not (i+j=0) do begin

e[a,i,j]:=true; e[a,j,i]:=true;

readln(i,j);

end;

end;

q[1].x:=1; q[1].y:=0; q[1].z:=0;

i:=1; j:=2;

while i

for a:=1 to n do if w[q[i].x,a] then begin

q[j].x:=a; q[j].y:=q[i].y+1; q[j].z:=q[i].z+1;

if q[j].y>t then q[j].y:=1;

if (e[q[j].y,q[i].x,a]=false) and (ch[q[j].y,q[i].x,a]=false) then begin if q[j].x=n then break

else begin

ch[q[j].y,q[i].x,a]:=true;

j:=j+1;

end;

end

else q[j].x:=0;

end;

if q[j].x=n then break;

i:=i+1;

end;

if q[j].x=n then writeln(q[j].z) else writeln('No solution.');

end.

程序3：

var t,b,c,d,e,l,h,k,m,n,min,r,o,z:longint; i,j:array[0..501] of longint;

p:array[0..501] of boolean;

a:array[0..101,0..101] of longint; f:array[0..101,0..11] of longint;

g:array[0..101,0..11,0..101] of longint; v,w:array[0..101] of longint;

begin

readln(n,m);

for b:=1 to m do begin

read(i[b],j[b]);

a[i[b],j[b]]:=b; a[j[b],i[b]]:=b; end;

readln(k);

for b:=1 to n do

for c:=1 to k do begin

g[b,c,0]:=1; g[b,c,1]:=b;

end;

if k=0 then begin k:=1; z:=1; end; for b:=1 to k do begin

fillchar(p,sizeof(p),0);

if z1 then begin

readln(c,d);

while (c0) or (d0) do begin p[a[c,d]]:=true;

readln(c,d);

end;

end;

for c:=1 to m do if not(p[c]) then begin inc(g[i[c],b,0]);

d:=g[i[c],b,0]; g[i[c],b,d]:=j[c]; inc(g[j[c],b,0]);

d:=g[j[c],b,0]; g[j[c],b,d]:=i[c]; end;

end;

f[1,k]:=1; c:=1; v[c]:=1; h:=0; while c0 do begin

d:=0; inc(h);

l:=(h-1) mod k+1;

for t:=1 to c do begin b:=v[t];

for e:=1 to g[b,l,0] do begin o:=g[b,l,e];

if f[o,l]=0 then begin

f[o,l]:=1; inc(d); w[d]:=o; if o=n then begin writeln(h); exit; end;

end;

end;

end;

v:=w; c:=d;

end;

writeln('No solution.');

end.