首页 > 代码库 > poj3259（Wormholes）

poj3259（Wormholes）

2024-07-07 12:27:29   233人阅读

题目大意：

     一个农夫在农场发现了许多奇怪的虫洞，这些虫洞是单向的，已知N个农场，M条正常的路径，W条虫洞，虫洞可以使时间倒流，农主通过正常的路径花费一定的时间，这个路径是双向的， 通过虫洞的路径可以使时间倒流，农主是狂热的旅行者，他的目的是通过正常路径和虫洞，能否回到最初的起点的时刻！

 

解题思路：

    bellman_ford算法，看是否有负权回路，有负权回路说明农主到达最初出发的农场“1”的权值小于0，也就意味着农主能通过虫洞的时光倒流回到最初出发农场的那个时刻，注意单向边和双向边，和数组的大小。

 

 代码：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <sstream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <string>
 8 #include <bitset>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <list>
14 #include <map>
15 #include <set>
16 using namespace std;
17 /***************************************/
18 #define ll long long
19 #define int64 __int64
20 /***************************************/
21 const int INF = 0x7f7f7f7f;
22 const double eps = 1e-8;
23 const double PIE=acos(-1.0);
24 const int d1x[]= {0,-1,0,1};
25 const int d1y[]= {-1,0,1,0};
26 const int d2x[]= {0,-1,0,1};
27 const int d2y[]= {1,0,-1,0};
28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
30 /***************************************/
31 void openfile()
32 {
33     freopen("data.in","rb",stdin);
34     freopen("data.out","wb",stdout);
35 }
36 /**********************华丽丽的分割线,以上为模板部分*****************/
37 struct no
38 {
39     int u,v;
40     int cost;
41 } node[6000];
42 int dis[550];
43 bool bellman_ford(int n,int edgenum)
44 {
45     int i,j;
46     for(i=1; i<=n; i++)
47         dis[i]=INF;
48     dis[1]=0;
49     for(i=1; i<=n-1; i++)
50         for(j=0; j<edgenum; j++)
51             if (dis[node[j].v]>dis[node[j].u]+node[j].cost)
52                 dis[node[j].v]=dis[node[j].u]+node[j].cost;
53     bool flag=0;
54     for(j=0; j<edgenum; j++)
55         if (dis[node[j].v]>dis[node[j].u]+node[j].cost)
56             flag=1;
57     return flag;
58 }
59 int main()
60 {
61     int cas;
62     scanf("%d",&cas);
63     while(cas--)
64     {
65         int n,m,w;
66         int i,j;
67         scanf("%d%d%d",&n,&m,&w);
68         int x,y,val;
69         int d=0;
70         for(i=0; i<m; i++)
71         {
72             scanf("%d%d%d",&x,&y,&val);
73             node[d].u=x;
74             node[d].v=y;
75             node[d].cost=val;
76             d++;
77             node[d].u=y;
78             node[d].v=x;
79             node[d].cost=val;
80             d++;
81         }
82         for(i=m; i<m+w; i++)
83         {
84             scanf("%d%d%d",&x,&y,&val);
85             node[d].u=x;
86             node[d].v=y;
87             node[d].cost=-val;
88             d++;
89         }
90         if (bellman_ford(n,d))
91             printf("YES\n");
92         else
93             printf("NO\n");
94     }
95     return 0;
96 }
View Code

 


联系
我们