本文共 3578 字，大约阅读时间需要 11 分钟。
农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。为了帮助FJ找出这是否是可以或不可以，他会为你提供F个农场的完整的映射到（1≤F≤5）。所有的路径所花时间都不大于10000秒，所有的虫洞都不大于万秒的时间回溯。Input第1行：一个整数F表示接下来会有F个农场说明。 每个农场第一行：分别是三个空格隔开的整数：N，M和W 第2行到M+1行：三个空格分开的数字（S，E，T）描述，分别为：需要T秒走过S和E之间的双向路径。两个区域可能由一个以上的路径来连接。 第M +2到M+ W+1行：三个空格分开的数字（S，E，T）描述虫洞，描述单向路径，S到E且回溯T秒。OutputF行，每行代表一个农场 每个农场单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。Sample Input
23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8
Sample Output
NOYES
Hint
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define mp make_pair#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxn = 1e5+20;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int tot,n,m,x,s;int u,v,w;int dis[maxn];int cnt[maxn],vis[maxn];struct cmp{ bool operator()(int a,int b) { return dis[a] > dis[b]; }};int head[maxn];struct node{ int v,w,nxt;}e[maxn];void init(){ tot=0; ms(cnt,0); ms(head,-1); ms(dis,INF);//求最长路径开始设为0 ms(vis,0);}void add(int u,int v,int w){ e[tot].v=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++;}int spfa(int s){ queue q; vis[s]=1; dis[s]=0; cnt[s]++; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u]=0; // for(int i=head[u];i!=-1;i=e[i].nxt) { int v = e[i].v; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); if(++cnt[v]>n) return 1;//有负环 } } } } return 0;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&w); init(); int a,b,c; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c); } for(int i=1;i<=w;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } if(spfa(1)) puts("YES"); else puts("NO"); }}/*【题意】【类型】SPFA判断负环【分析】spfa算法我们都知道spfa算法是对bellman算法的优化，那么如何用spfa算法来判断负权回路呢？我们考虑一个节点入队的条件是什么，只有那些在前一遍松弛中改变了距离估计值的点，才可能引起他们的邻接点的距离估计值的改变。因此，用一个先进先出的队列来存放被成功松弛的顶点。同样，我们有这样的定理：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）。也就是说，每个点最多入队n-1次（这里比较难理解，需要仔细体会，n-1只是一种最坏情况，实际中，这样会很大程度上影响程序的效率）。有了上面的基础，思路就很显然了，加开一个数组记录每个点入队的次数（num），然后，判断当前入队的点的入队次数，如果大于n-1，则说明存在负权回路。【时间复杂度&&优化】【trick】【数据】*/
转载于:https://www.cnblogs.com/Roni-i/p/9446542.html
