uva 10557

本文主要是介绍uva 10557，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：没两个点都有代权，可正可负，求是否可以从起点到终点，但我们会发现如果在一个点能够一直加能量，那就能让能量无穷大，所以此时这要判断是否能否到达终点就可以了，另一种情况就是在能量耗尽的时候能不能到达了。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 2145667886
using namespace std;int nRoom,energy[105];
struct Node
{int val;int nLeave;int reach[105];
};
Node room[105];
bool vis[105],flag;
int que[100000];void bfs(int pos)   //我们通过BFS来预判断是否可以到达终点
{memset(vis,0,sizeof(vis));vis[pos] = true;int front=0,rear=1;que[0] = pos;while ( front < rear ){int q = que[front++];if ( q == nRoom ){flag = true;return ;}for (int i = 0 ; i < room[q].nLeave ; i++){int m = room[q].reach[i];if ( !vis[m] && m>=1 && m<=nRoom ){vis[m] = true;que[rear++] = m ;}}}
}void dfs(int pos,int val)
{if ( flag || pos <=0 || pos > nRoom )return ;if  (val <= 0 )return ;if (pos == nRoom && val > 0 ){flag = true ;return ;}for (int i = 0 ; i < room[pos].nLeave ; i++){int m = room[pos].reach[i];if ( energy[m] && energy[m] < val+room[m].val )  //特判是否可以到达终点{bfs(pos);if (flag)return;}if ( !energy[m] && val+room[m].val>0 )   //用energy[]标记是否走过{energy[m] = val+room[m].val;dfs(m,val+room[m].val);}}
}int main()
{while (scanf("%d",&nRoom) != EOF && nRoom != -1){for (int i = 1 ; i <= nRoom ; i++){cin>>room[i].val>>room[i].nLeave;for (int j = 0 ; j < room[i].nLeave ; j++)cin>>room[i].reach[j];}memset(vis,0,sizeof(vis));memset(energy,0,sizeof(energy));energy[1] = 100 ;flag = false ;dfs(1,100);if ( flag )cout<<"winnable"<<endl;else cout<<"hopeless"<<endl;}return 0;
}

这篇关于uva 10557的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---