Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 501 Solved: 278
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的spfa只要判断下每个节点的入队次数,只要大于N,就可以判断有负环
1 /**************************************************************
2 Problem: 1715
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:160 ms
7 Memory:1060 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g,w:longint;
14 next:point;
15 end;
16 var
17 i,j,k,l,m,n,t:longint;
18 a:array[0..1500] of point;
19 b,c,g,e:array[0..1500] of longint;
20 d:array[0..100000] of longint;
21 procedure add(x,y,z:longint);
22 var p:point;
23 begin
24 new(p);p^.g:=y;p^.w:=z;p^.next:=a[x];a[x]:=p;
25 end;
26
27 function spfa(x:longint):boolean;
28 var f,r:longint;p:point;
29 begin
30 fillchar(e,sizeof(e),0);
31 fillchar(b,sizeof(b),0);
32 fillchar(g,sizeof(g),0);
33 for i:=1 to n do c[i]:=maxlongint div 2;
34 f:=1;r:=2;g[x]:=1;d[1]:=x;c[x]:=0;b[x]:=1;e[x]:=1;
35 while f<>r do
36 begin
37 p:=a[d[f]];
38 while p<>nil do
39 begin
40 if (e[p^.g]=0) or (c[p^.g]>(c[d[f]]+p^.w)) then
41 begin
42 e[p^.g]:=1;
43 c[p^.g]:=c[d[f]]+p^.w;
44 if g[p^.g]=0 then
45 begin
46 inc(b[p^.g]);
47 if b[p^.g]>n then exit(true);
48 g[p^.g]:=1;
49 d[r]:=p^.g;
50 r:=r mod 100000+1;
51 end;
52 end;
53 p:=p^.next;
54 end;
55 g[d[f]]:=0;f:=f mod 100000+1;
56 end;
57 exit(false);
58 end;
59 begin
60 readln(t);
61 while not(eof) do
62 begin
63 readln(n,m,t);
64 for i:=1 to n do a[i]:=nil;
65 for i:=1 to m do
66 begin
67 readln(j,k,l);
68 add(j,k,l);add(k,j,l);
69 end;
70 for i:=1 to t do
71 begin
72 readln(j,k,l);
73 add(j,k,-l);
74 end;
75 if spfa(1) then writeln('YES') else writeln('NO');
76 end;
77 end.