题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1317
题意是最多有100个房间,从1-n,然后每个房间都有一个能量值(可正可负),每到达一个房间就会获得这个房间的能量值,起点为1,刚开始会有100点能量值,问最后能不能到达n点且到达n点时还有没有能量值。
样例是多组输入n遇到-1结束,接下来n行中,第一个数表示从第i个房间到其他房间所能获得的能量值,第二个数m表示第i个房间能到达的房间数,然后m个房间编号。
思路是用spfa去跑最长路,然后在遇到正环的时候我们可以在这个正环里刷能量值,多在环里跑几圈,以至于能量值足够到达n点,其他没什么难点,主要就是跑正环的操作。
AC代码:
#include <bits/stdc++.h>
#define maxn 105
#define inf 105
using namespace std;
struct Node{
int to,w,next;
bool operator < (const Node &a) const{
return a.w < w;
}
}Edge[maxn * maxn];
int head[maxn * maxn],dist[maxn],cnt[maxn],num;
bool vis[maxn];
int n,m,x,v;
void init(){
for(int i=1;i<=maxn;i++)
cnt[i] = 0, head[i] = -1, dist[i] = 0, vis[i] = false;
num = 0;
}
void add(int u,int v,int w){
Edge[num].w = w;
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ++;
}
void spfa(){
dist[1] = 100;
queue<int> q;
q.push(1);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i=head[u];i!=-1;i=Edge[i].next){
int v = Edge[i].to;
if(dist[v] < dist[u] + Edge[i].w && cnt[v] < 10000){
cnt[v] ++;
dist[v] = dist[u] + Edge[i].w;
if(vis[v] == false){
vis[v] = true;
q.push(v);
}
}
}
}
if(dist[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++){
scanf("%d%d",&x,&m);
for(int j=0;j<m;j++){
scanf("%d",&v);
add(i, v, x);
}
}
spfa();
}
return 0;
}