首页 > 代码库 > poj 3259 Wormholes
poj 3259 Wormholes
题目链接：
http://poj.org/problem?id=3259
题目大意：
有一个穿越时光的农夫，他有N个农场，每个农场有M条双向路，有W个单向虫洞，每条路有三个属性（s，e，t）分别代表的是从s到达e花费t时间，每个虫洞也有三个属性（s，e，t）分别代表的是s到达e花费-t时间，这个农夫想要满足自己的穿越时光的梦想，他想在他的农场里游荡一圈以后回到原点并且看到原来的自己，如果能满足他的梦想就输出“YES”，否者“NO”。
解题思路：
可以看出这道题目就是判断所建图中有没有负权回路，用spfa就可以解决。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <vector> 5 #include <queue> 6 #include <cmath> 7 #include <iostream> 8 #include <algorithm> 9 using namespace std;10 #define maxn 51011 #define INF 0x3f3f3f3f12 13 struct Edge14 {15 int e, w;16 Edge(int e=0, int w=0) : e(e), w(w) {}17 };18 19 vector<Edge> G[maxn];20 int dist[maxn], n;21 void init ();22 bool spfa ();23 24 int main ()25 {26 int f;27 scanf ("%d", &f);28 while (f --)29 {30 int m, w, i;31 init ();32 scanf ("%d %d %d", &n, &m, &w);33 34 for (i=0; i<m; i++)35 {36 int a, b, c;37 scanf("%d %d %d", &a, &b, &c);38 G[a].push_back (Edge (b, c));39 G[b].push_back (Edge (a, c));40 }41 42 for (i=0; i<w; i++)43 {44 int a, b, c;45 scanf ("%d %d %d", &a, &b, &c);46 G[a].push_back (Edge (b, -c));47 }48 if (spfa ())49 printf ("NO\n");50 else51 printf ("YES\n");52 }53 return 0;54 }55 56 void init ()57 {58 for (int i=0; i<maxn; i++)59 dist[i] = INF, G[i].clear();60 }61 62 bool spfa ()63 {64 int updata[maxn];65 queue<Edge>que;66 Edge pn;67 pn.e = 1, pn.w = 0;68 memset (updata, 0, sizeof(updata));69 70 que.push(pn);71 dist[1] = 0;72 updata[pn.e] = 1;73 while ( !que.empty())74 {75 pn = que.front();76 que.pop();77 int len = G[pn.e].size();78 79 for (int i=0; i<len; i++)80 {81 Edge p = G[pn.e][i];82 if (dist[p.e] > dist[pn.e] + p.w)83 {84 dist[p.e] = dist[pn.e] + p.w;85 que.push(p);86 updata[p.e] ++;87 if (updata[p.e] == n)88 return false;89 }90 }91 }92 return true;93 }
poj 3259 Wormholes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。