POJ 3259 Wormholes(最短路Bellman_Ford)

Wormholes
 

大意:虫洞旅行,前面一部分(n组)是双向正权,后面一部分(w组)是单向负权,判断有没有负权环。

思路:由于有负权边,就不能Dijkstra了,用Bellman_Ford。就是看图中有没有负权环,有的话可以无限次走这个环,使得时间一定能得到一个负值。所以有的存在负环话就是可以,没有的话就是不可以了。

 
POJ 3259 Wormholes(最短路Bellman_Ford)
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define Max = 10001
 5 
 6 struct node
 7 {
 8     int s, e, t;
 9 } q[5010];
10 
11 int dis[520];
12 
13 bool Bellman_Ford(int n, int r)
14 {
15     memset(dis, 0, sizeof(dis));
16     for(int i = 1; i <= n; i++)
17     {
18         bool flag = false;
19         for(int j = 1; j <= r; j++)
20         {
21             if(dis[q[j].e] > dis[q[j].s]+q[j].t)
22             {
23                 dis[q[j].e] = dis[q[j].s]+q[j].t;
24                 flag = true;
25             }
26         }
27         if(!flag)
28         {
29             break;
30         }
31     }
32     for(int i = 1; i <= r; i++)
33     {
34         if(dis[q[i].e] > dis[q[i].s]+q[i].t)
35         {
36             return true;
37         }
38     }
39     return false;
40 }
41 
42 void Solve()
43 {
44     int p, n, m, w, a, b, c;
45     scanf("%d", &p);
46     while(p--)
47     {
48         scanf("%d%d%d", &n, &m, &w);
49         int r = 0;
50         for(int i = 1; i <= m; i++)
51         {
52             scanf("%d%d%d", &a, &b, &c);
53             q[++r].s = a;
54             q[r].e = b;
55             q[r].t = c;
56             q[++r].s = b;
57             q[r].e = a;
58             q[r].t = c;
59         }
60         for(int i = 1; i <= w; i++)
61         {
62             scanf("%d%d%d", &a, &b, &c);
63             q[++r].s = a;
64             q[r].e = b;
65             q[r].t = -c;
66         }
67         if(Bellman_Ford(n, r))
68         {
69             printf("YES\n");
70         }
71         else
72         {
73             printf("NO\n");
74         }
75     }
76 }
77 
78 int main()
79 {
80     Solve();
81 
82     return 0;
83 }
Wormholes

 

POJ 3259 Wormholes(最短路Bellman_Ford)

上一篇:HDU 3625 Examining the Rooms


下一篇:Java基础:请求重定向与请求转发的比较