解题思路：按照题目给定条件建图，判断能不能找到一条路到n，在这条路上权值和不会为负数，初始值为100.

只需要用spfa跑最长路，遇到正环的时候将当前节点到起点的距离置为 inf 即可。这样可以保证有正环的图一定可以得到解。

这道题的代码需要注意一些细节和剪枝。 /*

• @Author: wchhlbt
• @Last Modified time: 2017-09-20 */

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include

#define Fori(x) for(int i=0;i<x;i++) #define Forj(x) for(int j=0;j<x;j++) #define maxn 107 #define inf 0x3f3f3f3f #define ONES(x) __builtin_popcount(x) #define pb push_back #define AA first #define BB second #define _ << " " << using namespace std;

typedef long long ll ; const double eps =1e-8; const int mod = 998244353; const double PI = acos(-1.0); int dx[5] = {0,0,1,-1,0}; int dy[5] = {1,-1,0,0,0}; inline int read(){ int cnt; scanf("%d",&cnt); return cnt;}

//每次使用前需要调用init函数初始化 可以处理负权边 //最坏复杂度O(V*E) int d[maxn],inq[maxn];//inq数组储存当前点是否在队列中 int deg[maxn];//记录每个节点入队次数 vector e[maxn]; //pair<节点, 边权> int val[maxn]; int n,m; void init() { for(int i = 0; i<maxn; i++){ e[i].clear(); d[i] = -inf; inq[i] = 0; deg[i] = 0; } } void SPFA(int s)//s为起点 { queue Q; Q.push(s); d[s] = 100; inq[s] = 1; deg[s] = 1; while(!Q.empty()){ int hd = Q.front(); Q.pop(); inq[hd] = 0;
for(int i = 0; i<e[hd].size(); i++){ int u = e[hd][i]; int v = val[u]; if(d[u]<d[hd]+v && d[hd]+v>0){//注意这里的判断条件 d[u] = d[hd] + v; if(inq[u]==1 || deg[u]>n) continue;//注意这个地方的剪枝 inq[u] = 1; deg[u]++; if(deg[u]>n) d[u] = inf; Q.push(u); } } } if(d[n]>0) puts("winnable"); else puts("hopeless"); }

int main() { while(~scanf("%d",&n)) { if(n==-1) break; init(); for(int i = 1; i<=n; i++){ val[i] = read(); int num = read(); for(int j = 1; j<=num; j++){ int k = read(); e[i].pb(k); } } SPFA(1); } return 0; }