本文主要是介绍hdu 1317 XYZZY(spfa判环)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1317
大致题意：有n个房间，每个房间都有对应的能量值（可正可负），现在从1出发要到达n，初始能量为100，问是否能够达到n点，到达n的条件是中间及最后的能量值都要大于0.
思路：若不考虑环，那么求最长路判断是否大于0即可。若存在负环，对求最长路也没影响；但当存在正环时，最长路就不存在了。可用spfa判断，当某点入队超过n次，那么它必定在环中，直接将其dis置为INF，并不再将其近队列。最后若能到达n则可行，否则失败。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;int n;
int dis[maxn];
int inque[maxn];
int out[maxn];
vector <int> edge[maxn];
int w[maxn];bool spfa()
{queue <int> que;memset(dis,-INF,sizeof(dis));memset(inque,0,sizeof(inque));memset(out,0,sizeof(out));inque[1] = 1;dis[1] = 100;que.push(1);while(!que.empty()){int u = que.front();que.pop();inque[u] = 0;out[u]++;if(out[u] > n) //在环中不再仅队列continue;if(out[u] == n) //将dis置为INFdis[u] = INF;for(int i = 0; i < (int)edge[u].size(); i++){int v = edge[u][i];if(dis[v] < dis[u] + w[v] && dis[u] + w[v] > 0)//注意中间也要保证>0{dis[v] = dis[u] + w[v];if(v == n) //能够到达n返回truereturn true;if(!inque[v]){inque[v] = 1;que.push(v);}}}}return false;
}int main()
{int num,v;while(~scanf("%d",&n)){if(n == -1) break;for(int i = 1; i <= n; i++){edge[i].clear();scanf("%d",&w[i]);scanf("%d",&num);while(num--){scanf("%d",&v);edge[i].push_back(v);}}if(spfa())printf("winnable\n");else printf("hopeless\n");}return 0;
}这篇关于hdu 1317 XYZZY(spfa判环)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
