本文主要是介绍poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj 3259：
题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。
任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。
判断树中是否存在负权回路就ok了。
bellman代码：
#include<stdio.h>const int MaxN = 501;//农场数
const int INF = 0x3f3f3f3f;
int n;//点个数
int l;//边标记struct edge
{int from;int to;int len;
}e[5201];//2500条路径，2500*2条边+200个虫洞bool Bellman()
{int dis[MaxN];for(int i = 1; i <= n; i++)dis[i] = INF;dis[1] = 0;for(int i = 1; i < n; i++){bool over = true;//判断是否松弛完毕for(int j = 0; j < l; j++){int from = e[j].from;int to = e[j].to;int len = e[j].len;if(dis[from] != INF && dis[to] > dis[from] + len){dis[to] = dis[from] + len;over = false;}}if(over)break;}for(int j = 0; j < l; j++){int from = e[j].from;int to = e[j].to;int len = e[j].len;if(dis[to] > dis[from] + len)return true;}return false;
}int main()
{//freopen("in.txt", "r", stdin);int ncase;int m, w;scanf("%d", &ncase);while(ncase--){l = 0;scanf("%d%d%d", &n, &m, &w);int from, to, len;for(int i = 0; i < m; i++){scanf("%d%d%d", &from, &to, &len);e[l].from = from;e[l].to = to;e[l++].len = len;e[l].from = to;e[l].to = from;e[l++].len = len;}for(int i = 0; i < w; i++){scanf("%d%d%d", &from, &to, &len);e[l].from = from;e[l].to = to;e[l++].len = -len;}if(Bellman())printf("YES\n");elseprintf("NO\n");}return 0;
}
uva 558：
差不多的题目。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 1000 + 10;
const int maxm = 2000 + 10;
const int inf = 0x3f3f3f3f;struct Edge
{int fr, to, cost;
} e[maxm];int n, m;bool bellman()
{int dis[maxn];memset(dis, inf, sizeof(dis));dis[0] = 0;for (int i = 0; i < n - 1; i++){bool over = true;for (int j = 0; j < m; j++){int fr = e[j].fr;int to = e[j].to;int cost = e[j].cost;if (dis[fr] != inf && dis[fr] + cost < dis[to]){dis[to] = dis[fr] + cost;over = false;}}if (over)break;}for (int j = 0; j < m; j++){int fr = e[j].fr;int to = e[j].to;int cost = e[j].cost;if (dis[fr] + cost < dis[to])return true;}return false;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint ncase;scanf("%d", &ncase);while (ncase--){scanf("%d%d", &n, &m);for (int i = 0; i < m; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);e[i].fr = u;e[i].to = v;e[i].cost = w;
// e[i + m].fr = v;
// e[i + m].to = u;
// e[i + m].cost = w;}if (bellman())printf("possible\n");elseprintf("not possible\n");}return 0;
}
这篇关于poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
