首页 > 代码库 > HDU 1317 XYZZY
HDU 1317 XYZZY
题意是指 从1 到 N 能否保证 到达每个点的时候 能量都为正数。
起点 1 初始100 点能量。
输入是 从 1 ~ N , 分别是 能量,能到m个房间, 分别是 a1,a2,a3,…,am
可以给每个能到达的点 而 产生的边赋权,即能量值。
SPFA 求最长路的变形,出现负环不怕,出现正环就需要一点改动。
vis[]标记是否需要入队,d[] 表示能量,que[] 表示入队次数。
如果出现正环(que[v]>=n),表明一定能 保证到达每个点的时候都是正能量。
这时候直接 将 d[v] 赋最大值(因为可以一直循环获得正能量),并下一次的时候不再入队。
最后 d[n]>0 表明能行。
//C++ 0ms #include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0xfffffff #define eps 1e-6 using namespace std; int n,m; struct lx { int v,en; }; vector<lx> g[101]; int d[101]; bool vis[101]; int que[101]; void SPFA() { for(int i=1; i<=n; i++) d[i]=-INF,vis[i]=0,que[i]=0; queue<int>q; d[1]=100,vis[1]=1,que[1]=1; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; if(que[u]>n)continue;// >= WA for(int j=0; j<g[u].size(); j++) { int v=g[u][j].v; int en=g[u][j].en; if(d[v]<d[u]+en&&d[u]+en>0) { d[v]=d[u]+en; if(!vis[v]) { vis[v]=1; q.push(v); if(++que[v]>=n)d[v]=INF; } } } } if(d[n]>0)puts("winnable"); else puts("hopeless"); } int main() { while(scanf("%d",&n),n!=-1) { int en,v,u; for(int i=0; i<=n; i++) g[i].clear(); for(int i=1; i<=n; i++) { u=i; scanf("%d%d",&en,&m); lx now; now.en=en; while(m--) { scanf("%d",&v); now.v=v; g[u].push_back(now); } } SPFA(); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。