[BZOJ1715][Usaco2006 Dec]Wormholes 虫洞

本文主要是介绍[BZOJ1715][Usaco2006 Dec]Wormholes 虫洞，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[Usaco2006 Dec]Wormholes 虫洞

时间限制: 1 Sec 内存限制: 128 MB

题目描述

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

输入

Line 1: 一个整数 F, 表示农场个数。
Line 1 of each farm: 三个整数 N, M, W。
Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。
Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。
输出
Lines 1..F: 如果John能在这个农场实现他的目标，输出”YES”,否则输出”NO”。

样例输入

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

样例输出

NO
YES

SPFA判负环即可，据说写成BFS会快不少，有时间补上…

varw:array[0..100000,1..3]of longint;dist:array[0..10000]of longint;p:array[0..100000,1..2]of longint;t:array[0..1000000]of longint;i,j,l:longint;a,b,c,x,y,tt,k,f,key,v:longint;n,m,start,finish:longint;head,tail:longint;
beginreadln(f);for l:=1 to f dobeginfor i:=1 to k dobeginw[i,1]:=0;w[i,2]:=0;w[i,3]:=0;end;readln(n,m,v); k:=n+1;for i:=1 to m dobeginreadln(a,b,c);w[k,1]:=b;w[k,2]:=c;if w[a,3]=0then w[a,3]:=kelse w[w[a,1],3]:=k;w[a,1]:=k;inc(k);w[k,1]:=a;w[k,2]:=c;if w[b,3]=0then w[b,3]:=kelse w[w[b,1],3]:=k;w[b,1]:=k;inc(k);end;for i:=1 to v dobeginreadln(a,b,c);w[k,1]:=b;w[k,2]:=-c;if w[a,3]=0then w[a,3]:=kelse w[w[a,1],3]:=k;w[a,1]:=k;inc(k);end;start:=1; finish:=n;for i:=1 to n dodist[i]:=100000;for i:=1 to tail dobeginp[i,1]:=0;p[i,2]:=0;end;dist[start]:=0;head:=1; tail:=2; t[1]:=start; p[start,1]:=1; p[start,2]:=1; key:=0;while head<tail dobeginx:=head; y:=tail;for i:=head to tail-1 dobeginif p[t[head],2]>=nthen begin key:=1; break; end;tt:=w[t[i],3];while tt<>0 dobeginif dist[t[i]]+w[tt,2]<dist[w[tt,1]]thenbegindist[w[tt,1]]:=dist[t[i]]+w[tt,2];if p[w[tt,1],1]=0then begin t[y]:=w[tt,1]; p[w[tt,1],1]:=1; inc(p[w[tt,1],2]); inc(y); end;end;tt:=w[tt,3];end;inc(x);p[t[i],1]:=0;end;head:=x; tail:=y;if key=1 then break;end;if key=0then writeln('NO')else writeln('YES');end;
end.