不过 一次就过啦,真开心
题意 : 一个famer有一些农场,这些农场里面有一些田地,田地里面有一些虫洞,田地和田地之间有路,虫洞有这样的性质: 时间倒流。
问你这个农民能不能看到他自己,也就是说,有没有这样一条路径,能利用虫洞的时间倒流的性质,让这个人能在这个点出发前回去,这样他就是能看到他自己了。。。。。瀑布汗。。。。
输入 :
2 //农场个数 (text cases)
3 3 1 //田地 路径 虫洞 他们的个数
1 2 2 //田地路径 u, v, 以及经过需要的时间
1 3 4
2 3 1
3 1 3 //虫洞路径 u, v, 以及倒流的时间
3 2 1
1 2 3
2 3 4
3 1 8
想法: 首先建有向图,双向的路径也可以表示,然后倒流的时间设置为负权值。这样,就判断这个图里面有没有负回路就可以了
因为负回路就可以满足条件,代表总共的需要的时间是负的,也就是时间倒流了。
一次bellman。
Soure Code
1 #include <stdio.h>
2 #include <string.h>
3 #define max 10001
4 #define point 501
5 using namespace std;
6
7 struct E{
8 int u, v, w;
9 }e[25000];
10 int el, n, d[501];
11
12 void bellman(){
13 int i, j, f = 0;
14 for(i = 0; i < n - 1; i++){
15 f = 0;
16 for(j = 0; j < el; j++){
17 if(d[e[j].v] > d[e[j].u] + e[j].w){
18 d[e[j].v] = d[e[j].u] + e[j].w;
19 f = 1;
20 }
21 }
22 if(!f){
23 puts("NO");
24 return;
25 }
26 }
27 for(i = 0; i < el; i++){
28 if(d[e[i].v] > d[e[i].u] + e[i].w){
29 puts("YES");
30 return;
31 }
32 }
33 puts("NO");
34 }
35
36 int main(){
37 int i, j, m, w, u, v, W, F;
38 scanf("%d", &F);
39 while(F--){
40 el = 0;
41 scanf("%d%d%d", &n, &m, &w);
42 for(i = 0; i < m; i++){
43 scanf("%d%d%d", &u, &v, &W);
44 e[el].u = u;
45 e[el].v = v;
46 e[el++].w = W;
47 e[el].u = v;
48 e[el].v = u;
49 e[el++].w = W;
50 }
51 for(i = 0; i < w; i++){
52 scanf("%d%d%d", &u, &v, &W);
53 e[el].u = u;
54 e[el].v = v;
55 e[el++].w = -W;
56 }
57 bellman();
58 }
59 return 0;
60 }
61
62