Wormholes
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 16899 |
|
Accepted: 5961 |
Description
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.
Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output
Lines 1..F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).
Sample Input
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
Sample Output
NO
YES
这个题跟poj1860，poj2240本质是一样的，都是求有无负权回路
构图时候把每个虫洞的边的边值w存为-w，注意普通路径是双向边
bellford求负权回路原理：如果无向图边上存在负权回路，则回路边上的边（u,v）的d[v]值一定小于d[u]+w[u,v]。
如果写spfa的话，记下每个节点的入队次数，如果某个节点的入队次数超过n次的话，就说明存在负权回路
其实我是各种不明白……
1
#include<stdio.h>
2#include<string.h>
3#include<math.h>
4#define MAX 30000
5struct node
6
{
7
int h1,t1,len;
8
};
9struct node bb[MAX+5];
10int s,d[1000];
11int n,m,w;
12void init()
13{
14 int a,b,c;
15 int i;
16 s=0;
17 memset(bb,0,sizeof(bb));
18 scanf("%d%d%d",&n,&m,&w);
19 for (i=1; i<=m ; i++ )
20
{
21 scanf("%d%d%d",&a,&b,&c);
22 s++;
23 bb[s].h1=a;
24 bb[s].t1=b;
25 bb[s].len=c;
26 s++;
27 bb[s].h1=b;
28 bb[s].t1=a;
29 bb[s].len=c;
30
}
31 for (i=1; i<=w ; i++ )
32 {
33 scanf("%d%d%d",&a,&b,&c);
34 s++;
35 bb[s].h1=a;
36 bb[s].t1=b;
37 bb[s].len=-c;
38 }
39}
40void bellman_ford()
41{
42 int i,j,flag;
43 memset(d,0,sizeof(d));
44 for (i=1; i<=n; i++)
45 {
46 flag=0;
47 for (j=1; j<=s; j++)
48 if (d[bb[j].h1]+bb[j].len<d[bb[j].t1])
49 {
50 d[bb[j].t1]=d[bb[j].h1]+bb[j].len;
51 }
52 }
53 /**///////找有无负权回路
54 for (i=1; i<=s ; i++ )
55 if (d[bb[i].h1]+bb[i].len<d[bb[i].t1])
56 {
57 printf("YES\n");
58 return;
59 }
60 printf("NO\n");
61}
62int main()
63{
64 int t;
65 scanf("%d",&t);
66 while (t>0)
67 {
68 init();
69 bellman_ford();
70 t--;
71 }
72 return 0;
73}
74