poj 3259 Wormhole【bellman_ford】

港控/mmm° 2022-08-10 00:46 145阅读 0赞

Wormholes

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 37995</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 13992</td> 
  </tr> 
 </tbody> 
</table>

题目大意：约翰的农场有n块地，有m条双向的路（权值为正，即时间在流逝），有w个虫洞【单向路】（权值为负，即时间倒退），问，从任意一点开始，能回到过去么？

题目分析：n块地看做n个点，然后有2 \* m条权值为正的边，再有w条权值为负的边，形成一个图，问图中是否存在负环

已Accept代码\[【c++提交】：

#include <cstdio>
    #include <cstring>
    #define maxn 100000
    #define INF 0x3f3f3f3f
    using namespace std;
    
    int n, m, w;//点的个数，双向道路的条数，单向道路的条数 
    
    typedef struct Edge {
    	int x, y, t;//起点，终点，权值 
    }Edge;
    
    Edge edge[maxn];
    int dis[maxn];
    
    void relax(int x, int y, int t) {//松弛 
    	if(dis[y] > dis[x] + t)
    		dis[y] = dis[x] + t;
    }
    
    bool Beelman() {
    	for(int i = 1; i <= n - 1; ++i)
    		for(int j = 1; j <= 2 * m + w; ++j)
    			relax(edge[j].x, edge[j].y, edge[j].t);
    	bool flag = 1;
    	for(int i = 1; i <= 2 * m + w; ++i)// 判断是否有负环路
    		if(dis[edge[i].y] > dis[edge[i].x] + edge[i].t) {
    			flag = 0;
    			break;
    		}
    	return flag;
    }
    
    int main() {
    	int t;
    	scanf("%d", &t);
    	while(t--) {
    		scanf("%d%d%d", &n, &m, &w);
    		for(int i = 0; i <= n; i++)
    			dis[i] = INF;
    		dis[1] = 0;
    		for(int i = 1; i <= m * 2; i++) { //注意，是m条双向路，一条双向路 可以看成两条路 （a 到 b）  （b 到 a）； 
    			scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].t);
    			if(edge[i].x == 1)
    				dis[edge[i].y] = edge[i].t;
    			i++;
    			edge[i].x = edge[i - 1].y;
    			edge[i].y = edge[i - 1].x;
    			edge[i].t = edge[i - 1].t;
    			if(edge[i].x == 1)				//注意此处 
    				dis[edge[i].y] = edge[i].t;
    		}
    		for(int i = m * 2 + 1; i < m * 2 + 1 + w; i++) {
    			scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].t);
    			edge[i].t = (-1) * edge[i].t;
    			if(edge[i].x == 1)
    				dis[edge[i].y] = edge[i].t;
    		}
    		if(Beelman())
    			printf("NO\n");
    		else
    			printf("YES\n");
    	}
    	return 0;
    }