poj 3259 Wormholes（虫洞）

2019-11-06 07:46:48

字体：大中小

来源：转载

供稿：网友

题目题解代码

题目

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comPRises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds. 就是让找有没有负权回路，因为只要有负权回路，FJ就一定可以在0时刻之前回到起点

题解

判断有没有负权回路，用Bellman_ford 过程：做n次循环每一条边，判断是否可以用它更新到某个点的最短路然后判断是不是存在一条边每加一次都可以让最短路变小，若存在，则存在负权回路时间复杂度O(NE)。E为边数 $时间复杂度O(NE) 。 E为边数$

代码

var n,m,w,f,i,j,k,l:longint; e:array[1..3,1..6000]of longint; d:array[1..500]of longint;function bellman_ford(n,m:longint):boolean;var i,j,f:longint;begin fillchar(d,sizeof(d),$7f); d[1]:=0; for i:=1 to n do begin f:=1; for j:=1 to m do if d[e[2,j]]+e[3,j]<d[e[1,j]] then begin f:=0; d[e[1,j]]:=d[e[2,j]]+e[3,j]; end; if f=1 then break; end; for i:=1 to m do if d[e[2,i]]+e[3,i]<d[e[1,i]] then exit(false); exit(true);end;begin readln(f); for l:=1 to f do begin k:=0; readln(n,m,w); for i:=1 to m do begin inc(k); readln(e[1,k],e[2,k],e[3,k]); inc(k); e[1,k]:=e[2,k-1];e[2,k]:=e[1,k-1];e[3,k]:=e[3,k-1]; end; for i:=1 to w do begin inc(k); readln(e[1,k],e[2,k],j); e[3,k]:=-j; end; if bellman_ford(n,k) then writeln('NO') else writeln('YES'); end;end.

上一篇：采药（0/1背包）

下一篇：rust compiler and tools position in relative paths

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注