算法：最短路

求兩遍最短路，一個是從起點走向終點，另一個從終點走向起點，記錄下每次走每個點的最短路，然后枚舉一遍，對于每個點，找一個最大的最短路看能否更新min。

program P1356;constmaxn=10000;typeatp=recordy,dis,next:longint;end;varhead,tail,n,m,tot,st,ed:longint;b:array [0..maxn] of boolean;first,que:array [0..maxn] of longint;v:array [0..1,0..maxn] of longint;map:array [0..maxn] of atp;procedure init; vari,x,y,dis:longint; beginfillchar(v,sizeof(v),100);readln(n,m);for i:=1 to m dobeginreadln(x,y,dis);inc(tot);map[tot].y:=y;map[tot].dis:=dis;map[tot].next:=first[x];first[x]:=tot;inc(tot);map[tot].y:=x;map[tot].dis:=dis;map[tot].next:=first[y];first[y]:=tot;end;readln(st,ed); end;procedure SPFA(x:longint); vart:longint; beginfillchar(b,sizeof(b),false);fillchar(que,sizeof(que),0);if x=0 thenbeginv[x,st]:=0;que[1]:=st;b[st]:=true;endelsebeginv[x,ed]:=0;que[1]:=ed;b[ed]:=true;end;head:=0;tail:=1;while head<tail dobegininc(head);t:=first[que[head]];while t<>0 dobeginif v[x,que[head]]+map[t].dis<v[x,map[t].y] thenbeginv[x,map[t].y]:=v[x,que[head]]+map[t].dis;if not b[map[t].y] thenbegininc(tail);que[tail]:=map[t].y;b[map[t].y]:=true;end;end;t:=map[t].next;end;b[que[head]]:=false;end; end;function max(x,y:longint):longint; beginif x>y then exit(x) else exit(y); end;procedure outit; varmin,i:longint; beginmin:=maxlongint;for i:=1 to n do if max(v[0,i],v[1,i])<min then min:=max(v[0,i],v[1,i]);if min=v[0,0] then writeln('Peace!') else writeln(min); end;beginassign(input,'P1356.in'); reset(input);assign(output,'P1356.out'); rewrite(output);init;SPFA(0);SPFA(1);outit;close(input); close(output); end.

總結(jié)

以上是生活随笔為你收集整理的TYVJ1356（腾讯大战360）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。