同上题,不过改的spfa算法,注意每个节点进入队列的次数至多为n-1次(一共n个节点),若进入大于等于n次了,则说明图中存在负权回路,此时正好满足题目中时光倒流的要求,另外注意,vector每次用的时候清空。
下面是spfa算法的简单说明:
我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是松弛:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
注意对刚出队列的节点的所有相邻节点都要做松弛操作,不管该节点是否在队列中,不在队列中的松弛点加入到队列即可。
下面是spfa算法的简单说明:
我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是松弛:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
注意对刚出队列的节点的所有相邻节点都要做松弛操作,不管该节点是否在队列中,不在队列中的松弛点加入到队列即可。
#include <iostream> #include <fstream> #include <vector> #include <queue> #define INF 999999999 using namespace std; struct E { int v; int w; }edges[6000]; vector<E> v[1008]; bool visited[1008]; int dist[1008]; int enterCount[1008]; int n,m,w,edgeCount; void addEdge(int e,int s,int t) { edgeCount++; edges[edgeCount].v=s; edges[edgeCount].w=t; v[e].push_back(edges[edgeCount]); } bool spfa() { int i; queue<int> q; visited[1]=1; dist[1]=0; enterCount[1]=1; for(i=2;i<=n;i++) { visited[i]=0; dist[i]=INF; enterCount[i]=0; } q.push(1); while(!q.empty()) { int temp=q.front(); q.pop(); visited[temp]=0; for(i=0;i<v[temp].size();i++) { if(dist[v[temp][i].v]>dist[temp]+v[temp][i].w) { dist[v[temp][i].v]=dist[temp]+v[temp][i].w; if(!visited[v[temp][i].v]) { visited[v[temp][i].v]=1; enterCount[v[temp][i].v]++; if(enterCount[v[temp][i].v]>=n) return true; q.push(v[temp][i].v); } } } } return false; } int main() { //ifstream cin("1.txt"); int f,i; cin>>f; while(f--) { cin>>n>>m>>w; edgeCount=0; for(i=1;i<=n;i++) v[i].clear(); for(i=0;i<m;i++) { int s,e,t; cin>>s>>e>>t; addEdge(s,e,t); addEdge(e,s,t); } for(i=0;i<w;i++) { int s,e,t; cin>>s>>e>>t; addEdge(s,e,-t); } if(spfa()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
发表评论
-
2011清华考研机试题2
2011-08-09 14:56 905http://ac.jobdu.com/problem.php ... -
2011清华考研机试题1
2011-08-09 14:40 639题目描述 http://ac.jobdu.com/proble ... -
考研清华2011复试机考第三题
2011-08-09 13:51 1486题目描述 在某条线路上有N个火车站,有三种距离的路程,L1, ... -
poj3259 bellman水题
2011-08-08 17:04 967poj3259http://poj.org/problem?i ... -
acm题目常用的预处理
2011-08-08 15:26 1163#include<iostream> #in ... -
poj1860
2011-08-08 14:06 703poj1860http://poj.org/problem?i ... -
water~9
2011-08-06 18:01 416poj2109http://poj.org/problem?i ... -
water~8
2011-08-06 17:22 572poj2027http://poj.org/problem?i ... -
water~7
2011-08-06 17:15 567poj1328http://poj.org/problem?i ... -
water~6
2011-08-06 14:27 702poj1088http://poj.org/problem?i ... -
water~5
2011-08-06 14:24 580poj1003http://poj.org/problem?i ... -
water~4
2011-08-06 14:09 633poj1004http://poj.org/problem?i ... -
water~3
2011-08-06 13:59 522poj2159http://poj.org/problem?i ... -
water~2
2011-08-06 12:10 532poj3299http://poj.org/problem?i ... -
water~1
2011-08-06 10:35 639poj1503http://poj.org/problem?i ... -
POJ3280 简单DP
2011-08-05 14:48 890poj3280:http://poj.org/problem? ... -
POJ3253
2011-08-04 13:36 779poj3253:http://poj.org/problem? ...
相关推荐
北大POJ3259-Wormholes【Bellman】 解题报告+AC代码
POJ3259--Wormholes,使用bellman方法。
NULL 博文链接:https://taojianrong.iteye.com/blog/1756785
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1759266
北大POJ3096-Surprising Strings 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
此压缩包包含北京大学POJ题目的绝大部分解题代码,一道题目有不同语言的编程,但主要是C++语言,仅供大家学习之用。
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
poj分类poj分类poj分类poj分类
北大POJ2002-Squares 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告