| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 3694 | Accepted: 1059 |
Description
Input
Output
Sample Input
5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 -1
Sample Output
hopeless hopeless winnable winnable
题意:某人从 1走到 n,初始值为100，经过的每个点都有一个能量值,他走到每个点时会增加或者减少这个点的能量值,但是都不能小于 0 ，问他最后能否走到第n个点?
题解:spfa 判断正环,如果某个点的入队次数>n，那么则证明这个数赋值 INF ，然后这个点就不能进入了，然后每一次要判断是否大于 0
#include <iostream> #include <cstdio> #include <string.h> #include <queue> #include <algorithm> #include <math.h> using namespace std; typedef long long LL; const int INF = 999999999; const int N = 205; const int M = N*N; struct Edge{ int v,next; }edge[M]; int head[N]; int tot; int n; int val[N]; void addEdge(int u,int v,int &k){ edge[k].v = v,edge[k].next = head[u],head[u] = k++; } void init(){ memset(head,-1,sizeof(head)); tot = 0; } int low[N],time[N],pre[N]; bool vis[N]; bool spfa(int s){ for(int i=1;i<=n;i++){ vis[i] = false; low[i] = -INF; time[i] = 0; pre[i] = i; } low[s] = 100; time[s]++; queue<int> q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; if(time[u]>n) low[u] = INF; for(int k = head[u];k!=-1;k=edge[k].next){ int v = edge[k].v; if(low[v]<low[u]+val[v]&&low[u]+val[v]>0){ low[v] = low[u]+val[v]; if(!vis[v]&&time[v]<=n){ vis[v] = true; q.push(v); time[v]++; } } } } int temp = n; if(low[n]<=0) return false; return true; } int main(){ while(scanf("%d",&n)!=EOF,n!=-1){ init(); int num; for(int u=1;u<=n;u++){ scanf("%d%d",&val[u],&num); for(int j=1;j<=num;j++){ int v; scanf("%d",&v); addEdge(u,v,tot); } } if(spfa(1)) printf("winnable\n"); else printf("hopeless\n"); } return 0; }
原文：http://www.cnblogs.com/liyinggang/p/5698195.html